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

On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost

Author

Listed:
  • Han, Bin
  • Zhang, Wenjun
  • Lu, Xiwen
  • Lin, Yingzi

Abstract

This paper investigates minimization of both the makespan and delivery costs in on-line supply chain scheduling for single-machine and parallel-machine configurations in a transportation system with a single customer. The jobs are released as they arrive, which implies that no information on upcoming jobs, such as the release time, processing time, and quantity, is known beforehand to the scheduler. The jobs are processed on one machine or parallel machines and delivered to the customer. The primary objective of the scheduling is time, which is makespan in this case. The delivery cost, which changes due to the varying number of batches (though the cost for each batch is assumed to be the same) in delivery, is also concerned. The goal of scheduling is thus to minimize both the makespan and the total delivery cost. This scheduling involves deciding when to process jobs, which machine to process jobs, when to deliver jobs, and which batch to include jobs. We define 10 problems in terms of (1) the machine configuration, (2) preemption of job processing, (3) the number of vehicles, and (4) the capacity of vehicles. These problems (P1, P2, …, P10) have never been studied before in literature. The lower bound for each problem is first proved by constructing a series of intractable instances. Algorithms for these problems, denoted by H1, H2, …, H10, respectively, are then designed and a theoretical analysis is performed. The results show that H1, H2, H6, and H7 are optimal ones according to the competitive ratio criterion, while the other algorithms deviate slightly from the optimum. We also design the optimal algorithm for a special case of P5. A case study is provided to illustrate the performance of H5 and to demonstrate the practicality of the algorithms.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:244:y:2015:i:3:p:704-714
    DOI: 10.1016/j.ejor.2015.02.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715001058
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.02.008?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. 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.
    2. Zhi-Long Chen & George L. Vairaktarakis, 2005. "Integrated Scheduling of Production and Distribution Operations," Management Science, INFORMS, vol. 51(4), pages 614-628, April.
    3. Lingfa Lu & Jinjiang Yuan, 2008. "Single Machine Scheduling With Job Delivery To Minimize Makespan," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 25(01), pages 1-10.
    4. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    5. Nicholas G. Hall & Chris N. Potts, 2003. "Supply chain scheduling: Batching and delivery," Operations Research, INFORMS, vol. 51(4), pages 566-584, August.
    6. Baghalian, Atefeh & Rezapour, Shabnam & Farahani, Reza Zanjirani, 2013. "Robust supply chain network design with service level against disruptions and demand uncertainties: A real-life case," European Journal of Operational Research, Elsevier, vol. 227(1), pages 199-215.
    7. Meisel, Frank & Kirschstein, Thomas & Bierwirth, Christian, 2013. "Integrated production and intermodal transportation planning in large scale production–distribution-networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 62-78.
    8. 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.
    9. Zhi-Long Chen, 2010. "Integrated Production and Outbound Distribution Scheduling: Review and Extensions," Operations Research, INFORMS, vol. 58(1), pages 130-148, February.
    10. 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.
    11. 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.
    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. 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.
    2. Zhang, Jun & Wang, Xuping & Huang, Kai, 2018. "On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity," Omega, Elsevier, vol. 79(C), pages 104-115.
    3. Baş, Seda & Carello, Giuliana & Lanzarone, Ettore & Yalçındağ, Semih, 2018. "An appointment scheduling framework to balance the production of blood units from donation," European Journal of Operational Research, Elsevier, vol. 265(3), pages 1124-1143.
    4. Mohammad Ali Beheshtinia & Parisa Feizollahy & Masood Fathi, 2021. "Supply Chain Optimization Considering Sustainability Aspects," Sustainability, MDPI, vol. 13(21), pages 1-23, October.
    5. Li, Yantong & Côté, Jean-François & Coelho, Leandro C. & Zhang, Chuang & Zhang, Shuai, 2023. "Order assignment and scheduling under processing and distribution time uncertainty," European Journal of Operational Research, Elsevier, vol. 305(1), pages 148-163.
    6. Gianluca Nastasi & Valentina Colla & Silvia Cateni & Simone Campigli, 2018. "Implementation and comparison of algorithms for multi-objective optimization based on genetic algorithms applied to the management of an automated warehouse," Journal of Intelligent Manufacturing, Springer, vol. 29(7), pages 1545-1557, October.
    7. Wenchao Yi & Yinzhi Zhou & Liang Gao & Xinyu Li & Chunjiang Zhang, 2018. "Engineering design optimization using an improved local search based epsilon differential evolution algorithm," Journal of Intelligent Manufacturing, Springer, vol. 29(7), pages 1559-1580, October.
    8. Jiang, Min & Huang, George Q., 2022. "Intralogistics synchronization in robotic forward-reserve warehouses for e-commerce last-mile delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    9. 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.
    10. Fu, Yaping & Wu, Di & Wang, Yan & Wang, Hongfeng, 2020. "Facility location and capacity planning considering policy preference and uncertain demand under the One Belt One Road initiative," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 172-186.
    11. Feng Guo & Qi Liu & Dunhu Liu & Zhaoxia Guo, 2017. "On Production and Green Transportation Coordination in a Sustainable Global Supply Chain," Sustainability, MDPI, vol. 9(11), pages 1-20, November.
    12. Zhang, Jun & Liu, Feng & Tang, Jiafu & Li, Yanhui, 2019. "The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 180-199.
    13. Berghman, Lotte & Kergosien, Yannick & Billaut, Jean-Charles, 2023. "A review on integrated scheduling and outbound vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 311(1), pages 1-23.
    14. Yu, Yang & Wu, Yuting & Wang, Junwei, 2019. "Bi-objective green ride-sharing problem: Model and exact method," International Journal of Production Economics, Elsevier, vol. 208(C), pages 472-482.

    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. 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.
    2. Liang-Liang Fu & Mohamed Ali Aloulou & Christian Artigues, 2018. "Integrated production and outbound distribution scheduling problems with job release dates and deadlines," Journal of Scheduling, Springer, vol. 21(4), pages 443-460, August.
    3. 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.
    4. 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.
    5. Zeynep Ceylan & Hakan Tozan & Serol Bulkan, 2021. "A coordinated scheduling problem for the supply chain in a flexible job shop machine environment," Operational Research, Springer, vol. 21(2), pages 875-900, June.
    6. S. Mohammadi & S. Al-E-Hashem & Yacine Rekik, 2020. "An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company," Post-Print hal-02194222, HAL.
    7. Dmitry Ivanov & Richard Hartl & Alexandre Dolgui & Alexander Pavlov & Boris Sokolov, 2015. "Integration of aggregate distribution and dynamic transportation planning in a supply chain with capacity disruptions and the ripple effect consideration," International Journal of Production Research, Taylor & Francis Journals, vol. 53(23), pages 6963-6979, December.
    8. Feng Guo & Qi Liu & Dunhu Liu & Zhaoxia Guo, 2017. "On Production and Green Transportation Coordination in a Sustainable Global Supply Chain," Sustainability, MDPI, vol. 9(11), pages 1-20, November.
    9. 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.
    10. 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.
    11. 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.
    12. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.
    13. Zhang, Jun & Liu, Feng & Tang, Jiafu & Li, Yanhui, 2019. "The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 180-199.
    14. Ali Gharaei & Fariborz Jolai, 2021. "A Pareto approach for the multi-factory supply chain scheduling and distribution problem," Operational Research, Springer, vol. 21(4), pages 2333-2364, December.
    15. Mohammadi, S. & Al-e-Hashem, S.M.J. Mirzapour & Rekik, Y., 2020. "An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company," International Journal of Production Economics, Elsevier, vol. 219(C), pages 347-359.
    16. Azeddine Cheref & Alessandro Agnetis & Christian Artigues & Jean-Charles Billaut, 2017. "Complexity results for an integrated single machine scheduling and outbound delivery problem with fixed sequence," Journal of Scheduling, Springer, vol. 20(6), pages 681-693, December.
    17. 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.
    18. Li, Feng & Xu, Shifu & Xu, Zhou, 2023. "New exact and approximation algorithms for integrated production and transportation scheduling with committed delivery due dates and order acceptance," European Journal of Operational Research, Elsevier, vol. 306(1), pages 127-140.
    19. Daniel Schubert & André Scholz & Gerhard Wäscher, 2017. "Integrated Order Picking and Vehicle Routing with Due Dates," FEMM Working Papers 170007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    20. 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.

    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:244:y:2015:i:3:p:704-714. 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.