Two-machine open shop problem with controllable processing times

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

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
Volume4
Issue number2
DOIs
Publication statusPublished - 1 Jun 2007

Keywords

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

ASJC Scopus subject areas

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

Cite this