Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


In this paper we study both the non-preemptive and preemptive versions of the popular unit-time open shop scheduling problem. For the set of feasible schedules which satisfy a predetermined order of job completion times, we construct the linear description of the convex hull of the vectors of the job completion times. Based on the properties of the resulting scheduling polyhedron, we show that the problem of constructing an optimal schedule minimizing an arbitrary non-decreasing separable cost function of job completion times is polynomially solvable.
Original languageEnglish
Pages (from-to)444-456
Number of pages13
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 1 Sep 2005


  • Open shop scheduling
  • Parallel machine scheduling
  • Scheduling
  • Separable non-decreasing function

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this