Skip navigation
Please use this identifier to cite or link to this item:
Title: Sequence-dependent setup and removal times in a two-machine job-shop with minimizing the schedule length
Authors: Egorova, N. G.
Sotskov, Y. N.
Lai, T.-C.
Werner, Frank
Keywords: публикации ученых;scheduling theory;setup;job-shop
Issue Date: 2006
Publisher: Otto-von-Guericke-Universität
Citation: Egorova, N. G. Sequence-dependent setup and removal times in a two-machine job-shop with minimizing the schedule length / N. G. Egorova and others // Otto-von-Guericke-Universitet. - № 38. - Magdeburg, 2006. – 10 p.
Abstract: This article addresses the job-shop problem of minimizing the schedule length (makespan) for processing n jobs on two machines with sequence-dependent setup and removal times. The processing of each job includes at most two operations that have to be non-preemptive. Machine routes may differ from job to job. If all setup and removal times are equal to zero, this problem is polynomially solvable via Jackson's pair of job permutations, otherwise it is NP-hard even if each of n jobs consists of one operation on the same machine. We present sufficient conditions when Jackson's pair of permutations may be used for solving the two-machine job-shop problem with sequence-dependent setup and removal times. For the general case of this problem, the results obtained provide polynomial lower and upper bounds for the objective function value which are used in a branch-and-bound algorithm. Computational experiments show that an exact solution for this problem may be obtained in a suitable time for n ≤ 280. We also develop a heuristic algorithm and present a worst case analysis for it.
Appears in Collections:Публикации в зарубежных изданиях

Files in This Item:
File Description SizeFormat 
031022.pdf496.09 kBAdobe PDFView/Open
Show full item record Google Scholar

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.