Results - Details
Search command : Author="Kopidakis"
And Author="Yannis"
Current Record: 1 of 1
|
|
| 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
|
School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses
|
|
|
Type of Work--Post-graduate theses
|
| Permanent Link |
https://elocus.lib.uoc.gr//dlib/f/8/a/metadata-dlib-1993kopidakis.tkl
|
| Views |
488 |
Search
