Premium
Single batch machine scheduling with deliveries
Author(s) -
Cheng B.Y.,
Leung J.Y.T.,
Li K.,
Yang S.L.
Publication year - 2015
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21641
Subject(s) - scheduling (production processes) , computer science , schedule , full service , job scheduler , batch production , span (engineering) , due date , service (business) , plan (archaeology) , batch processing , job shop scheduling , operations research , customer service , real time computing , mathematical optimization , operations management , mathematics , operating system , engineering , business , marketing , cloud computing , history , civil engineering , archaeology , commerce
We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p j and a size s j . All jobs are available for processing at time 0. The batch machine has a capacity D . Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D . The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K . We assume that K = rD , where r ≥ 2 and r is an integer. The travel time of the vehicle is T ; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in O ( n log n ) time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in O ( n log n ) time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in O ( n log n ) time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015