| Abstract |
We consider the problem of minimizing the total completion time of n jobs on one machine with set-up times. All jobs have deterministic processing times, not necessarily identical, are available at time zero and belong to B different groups. Sequence independent set-up times are needed to adjust the machine when switching from jobs in one group to another. No preemption is allowed and jobs in a group need not be processed consecutively. The problem of total completion time of jobs on one machine ofter arises in detailed production planning. The algorithms developed here are embedded in an interactive production planning system, in the context of which the optimal or near-optimal solutions they produce can be modified before being committed as production schedules. The distribution of jobs into groups is taken into account for the solution of the problem and we try to construct subsets of jobs that are executed consecutively in an optimal sequence. Such subsets are called lots and are distinguished into first-order lots (FL), second - order lots (SL) and generalized lots (GL). We obtain propositions for the above entities and characteristics of the optimal solutions. The problem we study is very simple when no set-up times are considered, or when maximal generalized lots are known (it is solved in 0(nlogn) time). In the presence of set-up times the problem becomes more difficult, and its complexity has not been determined so far. Our contribution to the solution of the problem is the construction of three algorithms, one exact and two approximate. The exact one is a dynamic programming algorithm, eventually overwhelmed mostly by memory requirements as the number of groups grows. Using the proposition related to lot construction reduces memory requirements significantly and enables the solution of problems including 200-300 jobs distributed in 10-30 groups. On the other hand, the approximate algorithms can solve problems of larger dimensions. The first starts with an initial solution sharing several properties of the optimal and improves on it by combining SL into GL and maintaining a rule related to an optimal ordering of maximal GL. This algorithm is polynomial and has been experimentally observed to produce solutions with worst deviation from the optimum less that 2.4%. Many of the test problems (~73%) were solved optimally, while the average deviation from the optimum of the rest was 0.18%. The second approximate algorithm was inspired by the study and implementation of the polynomial algorithm of Ahn and Hyun for the same problem, along with the experimental study of our first approximate algorithm. The second algorithm is actually an apposition of i) the first approximate algorithm, ii) a procedure that analyzes the maximal GL of (i) into the constituent FL and iii) the algorithm of Ahn and Hyun, without the initial-sequence-construction step. This algorithm is also polynomial as apposition of two polynomial algorithms and one polynomial procedure. It has been observed to yield optimal solutions for the entire set of test problems.
|
Το Πρόβλημα του Συνολικού Χρόνου Περάτωσης Ν Εργασιών σε μια Μηχανή με Χρόνους Εξάρμωσης
