Inhaltszusammenfassung

This article deals with the scheduling problem of minimizing the makespan in a two-machine job-shop with given w intervals of machine non-availability. It is known that this problem is binary (unary) NP-hard if there is at least one non-availability interval (if the number of non-availability intervals may be arbitrarily large), and all the jobs have the same machine route. We find sufficient conditions when Jackson's pair of permutations remains optimal for the two-machine job-shop problem w...This article deals with the scheduling problem of minimizing the makespan in a two-machine job-shop with given w intervals of machine non-availability. It is known that this problem is binary (unary) NP-hard if there is at least one non-availability interval (if the number of non-availability intervals may be arbitrarily large), and all the jobs have the same machine route. We find sufficient conditions when Jackson's pair of permutations remains optimal for the two-machine job-shop problem with w⩾1 non-availability intervals. Extensive computational studies show the effectiveness (in the number of problems solved) and efficiency (in computational time) of these conditions for the randomly generated instances with up to 10,000 jobs and w⩾5000 non-availability intervals» weiterlesen» einklappen

Autoren

Klassifikation

DFG Fachgebiet:
Wirtschaftswissenschaften

DDC Sachgruppe:
Wirtschaft