TY - JOUR
T1 - Open Shop Scheduling with Synchronization
AU - Weiss, C.
AU - Waldherr, S.
AU - Knust, S.
AU - Shakhlevich, N. V.
PY - 2017/12
Y1 - 2017/12
N2 - In this paper, we study open shop scheduling problems with synchronization. This model has the same features as the classical open shop model, where each of the n jobs has to be processed by each of the m machines in an arbitrary order. Unlike the classical model, jobs are processed in synchronous cycles, which means that the m operations of the same cycle start at the same time. Within one cycle, machines which process operations with smaller processing times have to wait until the longest operation of the cycle is finished before the next cycle can start. Thus, the length of a cycle is equal to the maximum processing time of its operations. In this paper, we continue the line of research started by Weiß et al. (Discrete Appl Math 211:183–203, 2016). We establish new structural results for the two-machine problem with the makespan objective and use them to formulate an easier solution algorithm. Other versions of the problem, with the total completion time objective and those which involve due dates or deadlines, turn out to be NP-hard in the strong sense, even for m= 2 machines. We also show that relaxed models, in which cycles are allowed to contain less than m jobs, have the same complexity status.
AB - In this paper, we study open shop scheduling problems with synchronization. This model has the same features as the classical open shop model, where each of the n jobs has to be processed by each of the m machines in an arbitrary order. Unlike the classical model, jobs are processed in synchronous cycles, which means that the m operations of the same cycle start at the same time. Within one cycle, machines which process operations with smaller processing times have to wait until the longest operation of the cycle is finished before the next cycle can start. Thus, the length of a cycle is equal to the maximum processing time of its operations. In this paper, we continue the line of research started by Weiß et al. (Discrete Appl Math 211:183–203, 2016). We establish new structural results for the two-machine problem with the makespan objective and use them to formulate an easier solution algorithm. Other versions of the problem, with the total completion time objective and those which involve due dates or deadlines, turn out to be NP-hard in the strong sense, even for m= 2 machines. We also show that relaxed models, in which cycles are allowed to contain less than m jobs, have the same complexity status.
KW - Complexity
KW - Open shop
KW - Synchronization
UR - http://www.scopus.com/inward/record.url?scp=84981240511&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84981240511&partnerID=8YFLogxK
U2 - 10.1007/s10951-016-0490-0
DO - 10.1007/s10951-016-0490-0
M3 - Article
VL - 20
SP - 557
EP - 581
JO - Journal of Scheduling
JF - Journal of Scheduling
SN - 1094-6136
IS - 6
ER -