|Sequence-dependent setup times in a two-machine makespan job-shop scheduling problem
|Egorova, N. G.
Sotskov, Y. N.
|публикации ученых;планирование;одностадийное обслуживание требований;взвешенные моменты завершения обслуживания требований;устойчивость;неопределенность;интервальные длительности обслуживания требований;scheduling;single machine problems;total weighted completion times;stability;uncertainty;interval processing times
|Egorova, N. G. Sequence-dependent setup times in a two-machine makespan job-shop scheduling problem / N. G. Egorova, Y. N. Sotskov, F. Werner // ECCO XX-2007: 20th Anniversary Conference of the European Chapter on Combinatorial Optimization, – Cyprus, Limassol, (24–26 May 2007) / Center for Banking and Financial Research and Department of Public and Business Administration University of Cyprus. - Limassol, 2007. – Р. 30–31.
|job-shop problem of minimizing the schedule length (makespan) for processing n jobs on two machines with sequence-dependent setup times and removal times is consider. 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 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 permutations may be used for solving the two-machine job-shop problem with sequence-dependent setup times and removal times. For the general case of this problem, the results obtained provide polynomial lower and upper bounds for the makespan which are used in a branch-and-bound algorithm.
|Appears in Collections:
|Публикации в зарубежных изданиях
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.