TITLE

BATCH SIZING AND JOB SEQUENCING ON A SINGLE MACHINE

AUTHOR(S)
Coffman Jr., E. G.; Yannakakis, M.; Magazine, M. J.; Santos, C.
PUB. DATE
October 1990
SOURCE
Annals of Operations Research;1990, Vol. 26 Issue 1-4, p135
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
We study a single-machine scheduling problem in which the items to be processed have lo be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set of n items, the algorithm runs in O(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called the batch-sizing problem, runs in O(n log n) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].
ACCESSION #
18649762

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics