IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v135y2005i1p41-6410.1007-s10479-005-6234-8.html
   My bibliography  Save this article

The Coordination of Scheduling and Batch Deliveries

Author

Listed:
  • Nicholas Hall
  • Chris Potts

Abstract

This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment. Various scheduling costs, which are based on the delivery times of the jobs, are considered. The objective is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered. For many combinations of these, we either provide efficient algorithms that minimize total cost or show that the problem is intractable. Our work has implications for the coordination of scheduling with batch delivery decisions to improve customer service. Copyright Springer Science + Business Media, Inc. 2005

Suggested Citation

  • Nicholas Hall & Chris Potts, 2005. "The Coordination of Scheduling and Batch Deliveries," Annals of Operations Research, Springer, vol. 135(1), pages 41-64, March.
    • Handle: RePEc:spr:annopr:v:135:y:2005:i:1:p:41-64:10.1007/s10479-005-6234-8
    DOI: 10.1007/s10479-005-6234-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-005-6234-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-005-6234-8?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. Herrmann, Jeffrey W. & Lee, Chung-Yee, 1993. "On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date," European Journal of Operational Research, Elsevier, vol. 70(3), pages 272-288, November.
    2. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    3. Chung-Yee Lee & Reha Uzsoy & Louis A. Martin-Vega, 1992. "Efficient Algorithms for Scheduling Semiconductor Burn-In Operations," Operations Research, INFORMS, vol. 40(4), pages 764-775, August.
    4. Jianzhong Du & Joseph Y.-T. Leung, 1990. "Minimizing Total Tardiness on One Machine is NP-Hard," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 483-495, August.
    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. Wan, Long & Zhang, An, 2014. "Coordinated scheduling on parallel machines with batch delivery," International Journal of Production Economics, Elsevier, vol. 150(C), pages 199-203.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. George Steiner & Rui Zhang, 2011. "Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries," Annals of Operations Research, Springer, vol. 191(1), pages 171-181, November.
    7. Wang, Gang & Lei, Lei, 2012. "Polynomial-time solvable cases of the capacitated multi-echelon shipping network scheduling problem with delivery deadlines," International Journal of Production Economics, Elsevier, vol. 137(2), pages 263-271.
    8. Öncü Hazır & Safia Kedad-Sidhoum, 2014. "Batch sizing and just-in-time scheduling with common due date," Annals of Operations Research, Springer, vol. 213(1), pages 187-202, February.
    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. Wang, Xiuli & Cheng, T.C.E., 2009. "Logistics scheduling to minimize inventory and transport costs," International Journal of Production Economics, Elsevier, vol. 121(1), pages 266-273, September.
    11. Sağlam, Ümit & Banerjee, Avijit, 2018. "Integrated multiproduct batch production and truck shipment scheduling under different shipping policies," Omega, Elsevier, vol. 74(C), pages 70-81.
    12. Nodari Vakhania & Badri Mamporia, 2020. "Fast Algorithms for Basic Supply Chain Scheduling Problems," Mathematics, MDPI, vol. 8(11), pages 1-19, November.
    13. Elimam, A.A. & Dodin, B., 2013. "Project scheduling in optimizing integrated supply chain operations," European Journal of Operational Research, Elsevier, vol. 224(3), pages 530-541.
    14. Hongjun Wei & Jinjiang Yuan & Yuan Gao, 2019. "Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time," Mathematics, MDPI, vol. 7(9), pages 1-10, September.
    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. 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.
    17. Hua Gong & Lixin Tang & Joseph Y.T. Leung, 2016. "Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 492-502, September.
    18. Qi, Xiangtong, 2011. "Outsourcing and production scheduling for a two-stage flow shop," International Journal of Production Economics, Elsevier, vol. 129(1), pages 43-50, January.
    19. B.G. Khairov & D.T. Novikov & T.A. Prokof'yeva & I.O. Protsenko & S.M. Khairova, 2017. "Reflexive Governance of Import Substitution Mechanism in Clusters," European Research Studies Journal, European Research Studies Journal, vol. 0(3A), pages 470-483.

    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. 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.
    2. 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.
    3. A. G. Leeftink & R. J. Boucherie & E. W. Hans & M. A. M. Verdaasdonk & I. M. H. Vliegen & P. J. Diest, 2018. "Batch scheduling in the histopathology laboratory," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 171-197, June.
    4. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).
    5. Chang, Yung-Chia & Lee, Chung-Yee, 2004. "Machine scheduling with job delivery coordination," European Journal of Operational Research, Elsevier, vol. 158(2), pages 470-487, October.
    6. Lin, Ran & Wang, Jun-Qiang & Liu, Zhixin & Xu, Jun, 2023. "Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions," European Journal of Operational Research, Elsevier, vol. 309(1), pages 53-64.
    7. Lin, Ran & Wang, Jun-Qiang & Oulamara, Ammar, 2023. "Online scheduling on parallel-batch machines with periodic availability constraints and job delivery," Omega, Elsevier, vol. 116(C).
    8. Eduardo Queiroga & Rian G. S. Pinheiro & Quentin Christ & Anand Subramanian & Artur A. Pessoa, 2021. "Iterated local search for single machine total weighted tardiness batch scheduling," Journal of Heuristics, Springer, vol. 27(3), pages 353-438, June.
    9. Yuan Gao & Jinjiang Yuan, 2019. "Unbounded parallel-batch scheduling under agreeable release and processing to minimize total weighted number of tardy jobs," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 698-711, October.
    10. Kovalyov, M. Y. & Potts, C. N. & Strusevich, V. A., 2004. "Batching decisions for assembly production systems," European Journal of Operational Research, Elsevier, vol. 157(3), pages 620-642, September.
    11. Guruprasad Pundoor & Zhi‐Long Chen, 2005. "Scheduling a production–distribution system to optimize the tradeoff between delivery tardiness and distribution cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 571-589, September.
    12. Nodari Vakhania & Badri Mamporia, 2020. "Fast Algorithms for Basic Supply Chain Scheduling Problems," Mathematics, MDPI, vol. 8(11), pages 1-19, November.
    13. Chung Keung Poon & Wenci Yu, 2005. "On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity," Journal of Combinatorial Optimization, Springer, vol. 9(2), pages 167-186, March.
    14. Zhang, Hongbin & Yang, Yu & Wu, Feng, 2024. "Scheduling a set of jobs with convex piecewise linear cost functions on a single-batch-processing machine," Omega, Elsevier, vol. 122(C).
    15. Li, Shuguang, 2017. "Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan," European Journal of Operational Research, Elsevier, vol. 260(1), pages 12-20.
    16. Lin, B.M.T. & Cheng, T.C.E. & Chou, A.S.C., 2007. "Scheduling in an assembly-type production chain with batch transfer," Omega, Elsevier, vol. 35(2), pages 143-151, April.
    17. Li, Kai & Jia, Zhao-hong & Leung, Joseph Y.-T., 2015. "Integrated production and delivery on parallel batching machines," European Journal of Operational Research, Elsevier, vol. 247(3), pages 755-763.
    18. Damodaran, Purushothaman & Kumar Manjeshwar, Praveen & Srihari, Krishnaswami, 2006. "Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms," International Journal of Production Economics, Elsevier, vol. 103(2), pages 882-891, October.
    19. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    20. Li, Wenhua & Yuan, Jinjiang, 2006. "Single machine parallel batch scheduling problem with release dates and three hierarchical criteria to minimize makespan, machine occupation time and stocking cost," International Journal of Production Economics, Elsevier, vol. 102(1), pages 143-148, July.

    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:spr:annopr:v:135:y:2005:i:1:p:41-64:10.1007/s10479-005-6234-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.