TY - JOUR
T1 - Integrated scheduling on a batch machine to minimize production, inventory and distribution costs
AU - Cheng, Ba Yi
AU - Leung, Joseph Y.T.
AU - Li, Kai
N1 - Funding Information:
We would like to thank the three anonymous referees whose suggestions have greatly improved the readability of the paper. This work is partly supported by the National Natural Science Foundation of China under Grants 71531008 , 71671055 , 71601065 , 71131002 and 71471052 . This work is also partly supported by the Fundamental Research Funds for the Central Universities under Grant JZ2016HGTB0727.
Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2017/4/1
Y1 - 2017/4/1
N2 - We consider the problem of scheduling a set of jobs on a single batch-processing machine. Each job has a size and a processing time. The jobs are batched together and scheduled on the batch-processing machine, provided that the total size does not exceed the machine capacity. The processing time of the batch is the longest processing time among all the jobs in the batch. There is a single vehicle to deliver the final products to the customer. If the vehicle has not returned, completed batches will be put into the inventory. In this paper, we consider the problem of minimizing the production, delivery and inventory costs. We show that if the jobs have the same size, there is an O(nlog n)-time algorithm to find an optimal solution. If the jobs have the same processing time, there is a fast approximation algorithm with an absolute worst-case ratio less than 1.783 and an asymptotic worst-case ratio equal to 11/9. When the jobs have arbitrary sizes and arbitrary processing times, there is a fast approximation algorithm with absolute and asymptotic worst-case ratios less than or equal to 2, respectively.
AB - We consider the problem of scheduling a set of jobs on a single batch-processing machine. Each job has a size and a processing time. The jobs are batched together and scheduled on the batch-processing machine, provided that the total size does not exceed the machine capacity. The processing time of the batch is the longest processing time among all the jobs in the batch. There is a single vehicle to deliver the final products to the customer. If the vehicle has not returned, completed batches will be put into the inventory. In this paper, we consider the problem of minimizing the production, delivery and inventory costs. We show that if the jobs have the same size, there is an O(nlog n)-time algorithm to find an optimal solution. If the jobs have the same processing time, there is a fast approximation algorithm with an absolute worst-case ratio less than 1.783 and an asymptotic worst-case ratio equal to 11/9. When the jobs have arbitrary sizes and arbitrary processing times, there is a fast approximation algorithm with absolute and asymptotic worst-case ratios less than or equal to 2, respectively.
KW - Approximation algorithms
KW - Batch-processing machines
KW - Distribution
KW - Inventory
KW - Production
UR - http://www.scopus.com/inward/record.url?scp=84994514681&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84994514681&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2016.09.009
DO - 10.1016/j.ejor.2016.09.009
M3 - Article
AN - SCOPUS:84994514681
SN - 0377-2217
VL - 258
SP - 104
EP - 112
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -