We consider two single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. The problem has been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first problem (P1) we look at minimizing total completion time and number of tardy jobs for the two sets of jobs and present a forward SPT-EDD heuristic that attempts to generate the set of non-dominated solutions. The complexity of this specific problem is NP-hard; however some pseudo-polynomial algorithms have been suggested by earlier researchers and they have been used to compare the results from the proposed heuristic. In the second problem (P2) we look at minimizing total weighted completion time and maximum lateness. This is an established NP-hard problem for which we propose a forward WSPT-EDD heuristic that attempts to generate the set of supported points and compare our solution quality with MIP formulations. For both of these problems, we assume that all jobs are available at time zero and the jobs are not allowed to be preempted.

Original languageEnglish (US)
Pages (from-to)97-107
Number of pages11
JournalComputers and Operations Research
StatePublished - May 2014


  • Heuristic approaches
  • Interfering job sets
  • Mixed integer programming
  • Single machine scheduling

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Single machine scheduling with interfering job sets'. Together they form a unique fingerprint.

Cite this