Two-machine open shop problem with controllable processing times

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


We consider a two-machine open shop problem in which the job processing times are controllable and can be compressed while incurring additional costs. We show that the problem of minimizing a linear compression cost function for a given upper bound on the makespan can be solved in O (n) time. For the bicriteria problem of minimizing the makespan and compression cost, we propose an O (n log n) algorithm that finds all breakpoints of the efficient frontier.
Original languageEnglish
Pages (from-to)175-184
Number of pages10
JournalDiscrete Optimization
Issue number2
Publication statusPublished - 1 Jun 2007


  • Controllable processing times
  • Knapsack problem
  • Open shop scheduling
  • Resource allocation problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Two-machine open shop problem with controllable processing times'. Together they form a unique fingerprint.

Cite this