Bicriteria single-machine scheduling with multiple job classes and customer orders

Jatinder N.D. Gupta*, Chin Chia Wu, Win Chin Lin, Xin Gong Zhang, Danyu Bai, Bertrand M.T. Lin, Chia Cheng Liao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Customer order scheduling problems focus on completing all jobs of the same order consecutively to reduce the holding costs. Multiple job-class scheduling problems involving sequence independent family (class) setup times require completing all jobs of the same class consecutively to reduce the setup times. While these problems have been extensively studied in the literature, the scheduling problems jointly incorporating job classes and customer orders are relatively unexplored in the existing literature. Therefore, in this paper, we contribute to the existing literature by (1) addressing a single-machine scheduling problem involving multiple job classes with setup times and customer orders to minimize the bicriteria objective that is a linear combination of the makespan of all jobs and the sum of the holding costs of all orders; (2) proposing a mixed integer linear programming formulation; (3) developing a branch and bound algorithm that is equipped with a lower bound and two dominance properties to find an optimal solution needed to evaluate the effectiveness of the proposed heuristic algorithms; and (4) proposing six two-phase polynomially bounded heuristic algorithms and six variants of the water-wave optimization algorithms for producing approximate solutions The effectiveness and efficiency of the proposed algorithms are empirically evaluated through extensive computational experiments.

Original languageEnglish
Article number110809
JournalApplied Soft Computing
StatePublished - Nov 2023


  • Bicriteria scheduling
  • Customer order scheduling
  • Multiple job classes with setups
  • Two-phase heuristic algorithms
  • Water-wave optimization algorithms


Dive into the research topics of 'Bicriteria single-machine scheduling with multiple job classes and customer orders'. Together they form a unique fingerprint.

Cite this