Single-machine scheduling with trade-off between number of tardy jobs and resource allocation

Research output: Journal article publicationJournal articleAcademic researchpeer-review

29 Citations (Scopus)


We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.
Original languageEnglish
Pages (from-to)237-242
Number of pages6
JournalOperations Research Letters
Issue number5
Publication statusPublished - 1 Nov 1996


  • Resource allocation
  • Scheduling
  • Sequencing
  • Time-cost trade-offs

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Discrete Mathematics and Combinatorics
  • Modelling and Simulation

Cite this