Open Shop Scheduling with Synchronization

C. Weiss, S. Waldherr, S. Knust, N. V. Shakhlevich

Research output: Contribution to JournalArticleAcademicpeer-review


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.

Original languageEnglish
Pages (from-to)557-581
Number of pages25
JournalJournal of Scheduling
Issue number6
Publication statusPublished - Dec 2017
Externally publishedYes


The work of S. Knust and S. Waldherr was supported by the Deutsche Forschungsgemeinschaft, KN 512/7-1. The work of N.V. Shakhlevich was supported by the EPSRC grant EP/K041274/1. We are very grateful for the comments of two anonymous reviewers who helped us to improve the presentation of the paper.

FundersFunder number
Engineering and Physical Sciences Research CouncilEP/K041274/1
Deutsche ForschungsgemeinschaftKN 512/7-1


    • Complexity
    • Open shop
    • Synchronization


    Dive into the research topics of 'Open Shop Scheduling with Synchronization'. Together they form a unique fingerprint.

    Cite this