IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v258y2017i1p104-112.html
   My bibliography  Save this article

Integrated scheduling on a batch machine to minimize production, inventory and distribution costs

Author

Listed:
  • Cheng, Ba-Yi
  • Leung, Joseph Y-T.
  • Li, Kai

Abstract

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.

Suggested Citation

  • Cheng, Ba-Yi & Leung, Joseph Y-T. & Li, Kai, 2017. "Integrated scheduling on a batch machine to minimize production, inventory and distribution costs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 104-112.
    • Handle: RePEc:eee:ejores:v:258:y:2017:i:1:p:104-112
    DOI: 10.1016/j.ejor.2016.09.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716307457
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.09.009?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Zhi-Long Chen & George L. Vairaktarakis, 2005. "Integrated Scheduling of Production and Distribution Operations," Management Science, INFORMS, vol. 51(4), pages 614-628, April.
    2. Sung, C. S. & Min, J. I., 2001. "Scheduling in a two-machine flowshop with batch processing machine(s) for earliness/tardiness measure under a common due date," European Journal of Operational Research, Elsevier, vol. 131(1), pages 95-106, May.
    3. Osman, Hany & Demirli, Kudret, 2012. "Economic lot and delivery scheduling problem for multi-stage supply chains," International Journal of Production Economics, Elsevier, vol. 136(2), pages 275-286.
    4. Zhi-Long Chen & Nicholas G. Hall, 2007. "Supply Chain Scheduling: Conflict and Cooperation in Assembly Systems," Operations Research, INFORMS, vol. 55(6), pages 1072-1089, December.
    5. Bayi Cheng & Shanlin Yang & Xiaoxuan Hu & Kai Li, 2014. "Scheduling algorithm for flow shop with two batch-processing machines and arbitrary job sizes," International Journal of Systems Science, Taylor & Francis Journals, vol. 45(3), pages 571-578.
    6. Yeung, Wing-Kwan & Choi, Tsan-Ming & Cheng, T.C.E., 2011. "Supply chain scheduling and coordination with dual delivery modes and inventory storage cost," International Journal of Production Economics, Elsevier, vol. 132(2), pages 223-229, August.
    7. Leung, Joseph Y.-T. & Ng, C.T. & Cheng, T.C. Edwin, 2008. "Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1090-1099, June.
    8. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    9. Nicholas G. Hall & Chris N. Potts, 2003. "Supply chain scheduling: Batching and delivery," Operations Research, INFORMS, vol. 51(4), pages 566-584, August.
    10. Zhi-Long Chen & Guruprasad Pundoor, 2006. "Order Assignment and Scheduling in a Supply Chain," Operations Research, INFORMS, vol. 54(3), pages 555-572, June.
    11. Editors, 2014. "International Journal of Systems Science," International Journal of Systems Science, Taylor & Francis Journals, vol. 45(12), pages 1-1, December.
    12. Naso, David & Surico, Michele & Turchiano, Biagio & Kaymak, Uzay, 2007. "Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2069-2099, March.
    13. Averbakh, Igor & Xue, Zhihui, 2007. "On-line supply chain scheduling problems with preemption," European Journal of Operational Research, Elsevier, vol. 181(1), pages 500-504, August.
    14. Sawik, Tadeusz, 2009. "Coordinated supply chain scheduling," International Journal of Production Economics, Elsevier, vol. 120(2), pages 437-451, August.
    15. Esaignani Selvarajah & George Steiner, 2009. "Approximation Algorithms for the Supplier's Supply Chain Scheduling Problem to Minimize Delivery and Inventory Holding Costs," Operations Research, INFORMS, vol. 57(2), pages 426-438, April.
    16. Zhi-Long Chen, 2010. "Integrated Production and Outbound Distribution Scheduling: Review and Extensions," Operations Research, INFORMS, vol. 58(1), pages 130-148, February.
    17. Melouk, Sharif & Damodaran, Purushothaman & Chang, Ping-Yu, 2004. "Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing," International Journal of Production Economics, Elsevier, vol. 87(2), pages 141-147, January.
    18. Payman Jula & Robert C. Leachman, 2010. "Coordinated Multistage Scheduling of Parallel Batch-Processing Machines Under Multiresource Constraints," Operations Research, INFORMS, vol. 58(4-part-1), pages 933-947, August.
    19. Lixin Tang & Ying Meng & Zhi-Long Chen & Jiyin Liu, 2016. "Coil Batching to Improve Productivity and Energy Utilization in Steel Production," Manufacturing & Service Operations Management, INFORMS, vol. 18(2), pages 262-279, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sun, X.T. & Chung, S.H. & Chan, Felix T.S. & Wang, Zheng, 2018. "The impact of liner shipping unreliability on the production–distribution scheduling of a decentralized manufacturing system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 242-269.
    2. Cheng, Bayi & Zhu, Huijun & Li, Kai & Li, Yongjun, 2019. "Optimization of batch operations with a truncated batch-position-based learning effect," Omega, Elsevier, vol. 85(C), pages 134-143.
    3. Yong-Jae Kim & Byung-Soo Kim, 2022. "Population-Based Meta-Heuristic Algorithms for Integrated Batch Manufacturing and Delivery Scheduling Problem," Mathematics, MDPI, vol. 10(21), pages 1-22, November.
    4. Cheng, Bayi & Leung, Joseph Y.-T. & Li, Kai & Yang, Shanlin, 2019. "Integrated optimization of material supplying, manufacturing, and product distribution: Models and fast algorithms," European Journal of Operational Research, Elsevier, vol. 277(1), pages 100-111.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. B.‐Y. Cheng & J.Y.‐T. Leung & K. Li & S.‐L. Yang, 2015. "Single batch machine scheduling with deliveries," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(6), pages 470-482, September.
    2. Ullrich, Christian A., 2013. "Integrated machine scheduling and vehicle routing with time windows," European Journal of Operational Research, Elsevier, vol. 227(1), pages 152-165.
    3. Liang Tang & Zhihong Jin & Xuwei Qin & Ke Jing, 2019. "Supply chain scheduling in a collaborative manufacturing mode: model construction and algorithm design," Annals of Operations Research, Springer, vol. 275(2), pages 685-714, April.
    4. Esaignani Selvarajah & Rui Zhang, 2014. "Supply chain scheduling to minimize holding costs with outsourcing," Annals of Operations Research, Springer, vol. 217(1), pages 479-490, June.
    5. Nicholas G. Hall & Zhixin Liu, 2010. "Capacity Allocation and Scheduling in Supply Chains," Operations Research, INFORMS, vol. 58(6), pages 1711-1725, December.
    6. Tülin İnkaya & Mehmet Akansel, 2017. "Coordinated scheduling of the transfer lots in an assembly-type supply chain: a genetic algorithm approach," Journal of Intelligent Manufacturing, Springer, vol. 28(4), pages 1005-1015, April.
    7. Averbakh, Igor, 2010. "On-line integrated production-distribution scheduling problems with capacitated deliveries," European Journal of Operational Research, Elsevier, vol. 200(2), pages 377-384, January.
    8. Lixin Tang & Feng Li & Zhi-Long Chen, 2019. "Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and Online Algorithms," INFORMS Journal on Computing, INFORMS, vol. 31(3), pages 493-514, July.
    9. Xin Feng & Yongxi Cheng & Feifeng Zheng & Yinfeng Xu, 2016. "Online integrated production–distribution scheduling problems without preemption," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1569-1585, May.
    10. Han, Bin & Zhang, Wenjun & Lu, Xiwen & Lin, Yingzi, 2015. "On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost," European Journal of Operational Research, Elsevier, vol. 244(3), pages 704-714.
    11. Zhong, Xueling & Fan, Jie & Ou, Jinwen, 2022. "Coordinated scheduling of the outsourcing, in-house production and distribution operations," European Journal of Operational Research, Elsevier, vol. 302(2), pages 427-437.
    12. Lixin Tang & Feng Li & Jiyin Liu, 2015. "Integrated scheduling of loading and transportation with tractors and semitrailers separated," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(5), pages 416-433, August.
    13. Gao, Su & Qi, Lian & Lei, Lei, 2015. "Integrated batch production and distribution scheduling with limited vehicle capacity," International Journal of Production Economics, Elsevier, vol. 160(C), pages 13-25.
    14. Agnetis, Alessandro & Aloulou, Mohamed Ali & Fu, Liang-Liang, 2014. "Coordination of production and interstage batch delivery with outsourced distribution," European Journal of Operational Research, Elsevier, vol. 238(1), pages 130-142.
    15. Zhi-Long Chen, 2010. "Integrated Production and Outbound Distribution Scheduling: Review and Extensions," Operations Research, INFORMS, vol. 58(1), pages 130-148, February.
    16. Feng Li & Zhou Xu & Zhi-Long Chen, 2020. "Production and Transportation Integration for Commit-to-Delivery Mode with General Shipping Costs," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1012-1029, October.
    17. Liu, Weihua & Wang, Qian & Mao, Qiaomei & Wang, Shuqing & Zhu, Donglei, 2015. "A scheduling model of logistics service supply chain based on the mass customization service and uncertainty of FLSP’s operation time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 83(C), pages 189-215.
    18. Esaignani Selvarajah & George Steiner, 2009. "Approximation Algorithms for the Supplier's Supply Chain Scheduling Problem to Minimize Delivery and Inventory Holding Costs," Operations Research, INFORMS, vol. 57(2), pages 426-438, April.
    19. Jun Pei & Xinbao Liu & Panos M. Pardalos & Wenjuan Fan & Ling Wang & Shanlin Yang, 2016. "Solving a supply chain scheduling problem with non-identical job sizes and release times by applying a novel effective heuristic algorithm," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(4), pages 765-776, March.
    20. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:258:y:2017:i:1:p:104-112. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.