Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

José Elias C. Arroyo, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

71 Scopus citations


This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.

Original languageEnglish (US)
Pages (from-to)117-128
Number of pages12
JournalComputers and Operations Research
StatePublished - Feb 1 2017

All Science Journal Classification (ASJC) codes

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


  • Heuristics
  • Makespan
  • NP-hard
  • Scheduling
  • Unrelated parallel batch machines


Dive into the research topics of 'Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times'. Together they form a unique fingerprint.

Cite this