Your browser does not support JavaScript!

Home    Collections    Type of Work    Post-graduate theses  

Post-graduate theses

Search command : Author="Στεφανίδης"  And Author="Κωνσταντίνος"

Current Record: 4695 of 4817

Back to Results Previous page
Next page
Add to Basket
[Add to Basket]
Identifier uch.csd.msc//1993kopidakis
Title Αλγόριθμοι Παρεμβολής για το Πρόβλημα Ροϊκής Παραγωγής
Alternative Title Interpolation Algorithms for the Flowshop Scheduling Problem
Creator Kopidakis, Yannis
Abstract In the present study we consider the deterministic scheduling of N jobs in a flowshop of M machines with sequence indepedent setup times. Each job is further divided into M tasks and each task is executed on a different machine. The order of task execution is identical for each job. The N jobs are distributed over B groups and between two jobs of the same group no machine setup is neeeded. We deal with two different problems: the minimization of total execution time and the minimization of maximum job tardiness. The first problem is often discussed in the literature and belongs to the category of hard combinational problems. Many heuristic methids have been proposed to provide approximate solutions. For the second problem no algorithm is known. We selected the job insertion algorithm as a general schema for both problems. The job insertion method constructs the final program in N stages, always leading towards the best value of the optimality criterion. For the due date job scheduling we develop the feasible insertion method in order to produce feasible solutions with short total execution time, or, if this proves impossible, solutions with minimal job tardiness. In order words, the method performs bicriterion scheduling for the minimization of maximum tardiness and total execution time, providing absolute priority to the first criterion. In addition, we suggest two solution improvement mechanisms which are incorporated into the insertion procedure: the storage of a working set of partial sequences and the iterative insertion with random programming queues. In order to evaluate the performance of the improved insertion algorithms, we performed systematic tests with random problems of varying size. In this way, 2730 random problems were generated and 24660 solutions were produced by different algorithm versions (each problem was solved in about 9 different ways). For the minimazation of total execution time, we compared the insertion algorithms to the best known flowshop heuristic. The mean improvement reported was 20%-25% and in some cases it reached 45%. Yet, deviation from the optimum was not negligible, demonstrating the graet difficulty of the problem. The tests have highlighted that the number of machines (M) is most critical factor for the quality of solutions, due the presence of machine idle times. The tests related to the problem of maximum tardiness concerned the solution feasibility and the effectiveness of the new mechanisms. Finally, we present the conclusions on the performance of insertion algorithms for the flowshop problem, we discuss cases of low performance for jobs with due dates and we purpose ways of handling those. We also consider the application of the insertion algorithms in other deterministic scheduling problems.
Issue date 1993-12-01
Date available 1997-06-2
Collection   Faculty/Department--Faculty of Sciences and Engineering--Department of Computer Science--Post-graduate theses
  Type of Work--Post-graduate theses
Permanent Link Bookmark and Share
Views 220

Digital Documents
No preview available

View document
Views : 8

No preview available

View document