IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v14y2007i4d10.1007_s10878-007-9070-8.html
   My bibliography  Save this article

A note on special optimal batching structures to minimize total weighted completion time

Author

Listed:
  • Wenhua Li

    (Zhengzhou University)

  • Jinjiang Yuan

    (Zhengzhou University)

  • Yixun Lin

    (Zhengzhou University)

Abstract

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. The algorithmic aspects of the batching scheduling problems have been extensively studied in the literature. This paper presents necessary and sufficient conditions of the existence of optimal batch sequences for the single machine, batching, total weighted completion time scheduling problems on two batching ways: (1) all jobs form one batch; (2) each batch contains a single job. This kind of conditions can help us to recognize some special optimal schedules quickly.

Suggested Citation

  • Wenhua Li & Jinjiang Yuan & Yixun Lin, 2007. "A note on special optimal batching structures to minimize total weighted completion time," Journal of Combinatorial Optimization, Springer, vol. 14(4), pages 475-480, November.
    • Handle: RePEc:spr:jcomop:v:14:y:2007:i:4:d:10.1007_s10878-007-9070-8
    DOI: 10.1007/s10878-007-9070-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-007-9070-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-007-9070-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. 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.
    2. Yuan, J.J. & Lin, Y.X. & Cheng, T.C.E. & Ng, C.T., 2007. "Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time," International Journal of Production Economics, Elsevier, vol. 105(2), pages 402-406, February.
    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. Wenhua Li & Weina Zhai & Xing Chai, 2019. "Online Bi-Criteria Scheduling on Batch Machines with Machine Costs," Mathematics, MDPI, vol. 7(10), pages 1-11, October.
    2. Xing Chai & Wenhua Li & Yuejuan Zhu, 2021. "Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine," Annals of Operations Research, Springer, vol. 298(1), pages 79-93, March.

    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. Jun-Qiang Wang & Guo-Qiang Fan & Zhixin Liu, 2020. "Mixed batch scheduling on identical machines," Journal of Scheduling, Springer, vol. 23(4), pages 487-496, August.
    2. Jae-Min Yu & Rong Huang & Dong-Ho Lee, 2017. "Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops," International Journal of Production Research, Taylor & Francis Journals, vol. 55(11), pages 3266-3282, June.
    3. Otto, Alena & Li, Xiyu, 2020. "Product sequencing in multiple-piece-flow assembly lines," Omega, Elsevier, vol. 91(C).
    4. Jason Pan & Chi-Shiang Su, 2015. "Two parallel machines problem with job delivery coordination and availability constraint," Annals of Operations Research, Springer, vol. 235(1), pages 653-664, December.
    5. Altekin, F. Tevhide & Bukchin, Yossi, 2022. "A multi-objective optimization approach for exploring the cost and makespan trade-off in additive manufacturing," European Journal of Operational Research, Elsevier, vol. 301(1), pages 235-253.
    6. Elisabeth Lübbecke & Marco E. Lübbecke & Rolf H. Möhring, 2019. "Ship Traffic Optimization for the Kiel Canal," Operations Research, INFORMS, vol. 67(3), pages 791-812, May.
    7. Gahm, Christian & Uzunoglu, Aykut & Wahl, Stefan & Ganschinietz, Chantal & Tuma, Axel, 2022. "Applying machine learning for the anticipation of complex nesting solutions in hierarchical production planning," European Journal of Operational Research, Elsevier, vol. 296(3), pages 819-836.
    8. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.
    9. Shen, Liji & Buscher, Udo, 2012. "Solving the serial batching problem in job shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 14-26.
    10. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    11. Shisheng Li & T.C.E. Cheng & C.T. Ng & Jinjiang Yuan, 2017. "Two‐agent scheduling on a single sequential and compatible batching machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 628-641, December.
    12. Anurag Agarwal & Varghese S. Jacob & Hasan Pirkul, 2006. "An Improved Augmented Neural-Network Approach for Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 119-128, February.
    13. Cheng, T. C. Edwin & Janiak, Adam & Kovalyov, Mikhail Y., 2001. "Single machine batch scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 135(1), pages 177-183, November.
    14. 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.
    15. Vo[ss], Stefan & Witt, Andreas, 2007. "Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application," International Journal of Production Economics, Elsevier, vol. 105(2), pages 445-458, February.
    16. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    17. Chakhlevitch, Konstantin & Glass, Celia A. & Kellerer, Hans, 2011. "Batch machine production with perishability time windows and limited batch size," European Journal of Operational Research, Elsevier, vol. 210(1), pages 39-47, April.
    18. A. Dolgui & M. Kovalyov & K. Shchamialiova, 2011. "Multi-product lot-sizing and sequencing on a single imperfect machine," Computational Optimization and Applications, Springer, vol. 50(3), pages 465-482, December.
    19. Dunstall, Simon & Wirth, Andrew, 2005. "A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines," European Journal of Operational Research, Elsevier, vol. 167(2), pages 283-296, December.
    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:spr:jcomop:v:14:y:2007:i:4:d:10.1007_s10878-007-9070-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.