Scheduling parallel machines for the customer order problem

Jaehwan Yang, Marc E. Posner

Research output: Contribution to journalArticlepeer-review

48 Scopus citations


This paper considers scheduling problems where jobs are dispatched in batches. The objective is to minimize the sum of the completion times of the batches. While a machine can process only one job at a time, multiple machines can simultaneously process jobs in a batch. This simple environment has a variety of real world applications such as part kitting and customer order scheduling. A heuristic is presented for the parallel machine version of the problem. Also, a tight worst case bound on the relative error is found. For the case of two parallel machines, we examine two heuristics, which are based on simple scheduling rules. We find tight worst case bounds of 6/5 and 9/7 on the relative error and show that neither procedure is superior for all instances. Finally, we empirically evaluate these two heuristics. For large problems, the methods find solutions that are close to optimal.

Original languageEnglish
Pages (from-to)49-74
Number of pages26
JournalJournal of Scheduling
Issue number1
StatePublished - Jan 2005


  • Batch scheduling
  • Customer order scheduling
  • Heuristic analysis
  • Kitting


Dive into the research topics of 'Scheduling parallel machines for the customer order problem'. Together they form a unique fingerprint.

Cite this