Maximizing total job value on a single machine with job selection

Joonyup Eun, Chang Sup Sung, Eun Seok Kim

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


This paper describes a single-machine scheduling problem of maximizing total job value with a machine availability constraint. The value of each job decreases over time in a stepwise fashion. Several solution properties of the problem are developed. Based on the properties, a branch-And-bound algorithm and a heuristic algorithm are derived. These algorithms are evaluated in the computational study, and the results show that the heuristic algorithm provides effective solutions within short computation times.

Original languageEnglish
Pages (from-to)998-1005
Number of pages8
JournalJournal of the Operational Research Society
Issue number9
Publication statusPublished - 2017 Sept 1
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2017 The Operational Research Society.


  • branch-And-bound
  • heuristic
  • job value
  • scheduling
  • stepwise value function

ASJC Scopus subject areas

  • Modelling and Simulation
  • Strategy and Management
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research


Dive into the research topics of 'Maximizing total job value on a single machine with job selection'. Together they form a unique fingerprint.

Cite this