Scheduling to minimize the total compression and late costs

Edwin Tai Chiu Cheng, Zhi Long Chen, Chung Lun Li, B. M.T. Lin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

23 Citations (Scopus)


We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly.
Original languageEnglish
Pages (from-to)67-82
Number of pages16
JournalNaval Research Logistics
Issue number1
Publication statusPublished - 1 Jan 1998


  • Approximation schemes
  • Computational complexity
  • Dynamic programming
  • Scheduling
  • Sequencing

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Scheduling to minimize the total compression and late costs'. Together they form a unique fingerprint.

Cite this