An exact algorithm for batching and scheduling two part types in a mixed shop: A technical note

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)


We consider the problem of scheduling jobs consisting of two part types in a shop made up of three machines. The processing of each job comprises two stages. The first stage is undertaken on the machine common to all jobs and the second stage is undertaken on the machine specific to a particular part type. Set-up times are necessary at the first stage to switch processing from a job of one part type to a job of the other part type. Jobs of the same part type processed contiguously at the first stage form a batch. The objective is to find a batch schedule minimizing the makespan. An integer programming formulation and a heuristic algorithm for this problem have been reported in the literature. We present a dynamic programming algorithm which solves the problem optimally in a time polynomial in the number of jobs.
Original languageEnglish
Pages (from-to)53-56
Number of pages4
JournalInternational Journal of Production Economics
Issue number1
Publication statusPublished - 10 Jun 1998


  • Batching
  • Scheduling

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this