One-machine batching and sequencing of multiple-type items

Edwin Tai Chiu Cheng, Z. L. Chen, C. Oguz

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)


We consider a single-machine scheduling problem in which a given number of simultaneously available items of different types are to be processed. The items must first be batched and then sequenced before processing begins. Only items of the same type can be batched together. A setup time is incurred whenever a batch of a certain type of item is formed. The flowtime of an item in a batch is defined as the completion time of the batch that contains it. The problem is to find an optimal schedule in terms of the optimal batching and sequencing decisions that minimizes the total item flowtime. We present a dynamic programming algorithm to solve this problem. The algorithm has a running time polynomial in the number of items but exponential in the number of types.
Original languageEnglish
Pages (from-to)717-721
Number of pages5
JournalComputers and Operations Research
Issue number7
Publication statusPublished - 1 Jan 1994

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this