Scheduling with safety distances

F.C.R. Spieksma, G.J. Woeginger, Zhongliang Yu

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)


    We investigate the problem of Scheduling with Safety Distances (SSD) that consists in scheduling jobs on two parallel machines without machine idle time. Every job is already assigned to its machine, and we just have to specify an ordering of the jobs for each machine. The goal is to find orderings of the jobs such that the minimum time elapsed between any two job completion times is maximized. We prove that this problem is NP-hard in general and give polynomial time algorithms for special cases. These results combined establish a sharp borderline between NP-complete and polynomial solvable versions of the problem SSD.
    Original languageEnglish
    Pages (from-to)251-264
    JournalAnnals of Operations Research
    Issue number1
    Publication statusPublished - 1995


    Dive into the research topics of 'Scheduling with safety distances'. Together they form a unique fingerprint.

    Cite this