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

An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan

Author

Listed:
  • Yuzhong Zhang

    (Qufu Normal University)

  • Zhigang Cao

    (Academy of Mathematics and Systems Science, Chinese Academy of Sciences)

Abstract

Motivated by the existence of an APTAS (Asymptotic PTAS) for bin packing problem, we consider the batch scheduling problem with nonidentical job sizes to minimize makespan. For the proportional special version, i.e., there exists a fixed number α such that p j =α s j for every 1≤j≤n, we first present a lower bound of 3/2 for the approximation ratio and then design an APTAS.

Suggested Citation

  • Yuzhong Zhang & Zhigang Cao, 2008. "An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan," Journal of Combinatorial Optimization, Springer, vol. 16(2), pages 119-126, August.
    • Handle: RePEc:spr:jcomop:v:16:y:2008:i:2:d:10.1007_s10878-007-9128-7
    DOI: 10.1007/s10878-007-9128-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-007-9128-7
    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-9128-7?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. Jolai Ghazvini, Fariborz & Dupont, Lionel, 1998. "Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes," International Journal of Production Economics, Elsevier, vol. 55(3), pages 273-280, August.
    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. Guochuan Zhang & Xiaoqiang Cai & C.‐Y Lee & C.K Wong, 2001. "Minimizing makespan on a single batch processing machine with nonidentical job sizes," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(3), pages 226-240, April.
    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. 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.

    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. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).
    4. 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.
    5. Jia, Zhao-hong & Leung, Joseph Y.-T., 2015. "A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes," European Journal of Operational Research, Elsevier, vol. 240(3), pages 649-665.
    6. Gyorgy Dosa & Zhiyi Tan & Zsolt Tuza & Yujie Yan & Cecília Sik Lányi, 2014. "Improved bounds for batch scheduling with nonidentical job sizes," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(5), pages 351-358, August.
    7. Miaomiao Jin & Xiaoxia Liu & Wenchang Luo, 2020. "Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection," Mathematics, MDPI, vol. 8(2), pages 1-8, February.
    8. 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.
    9. Malapert, Arnaud & Guéret, Christelle & Rousseau, Louis-Martin, 2012. "A constraint programming approach for a batch processing problem with non-identical job sizes," European Journal of Operational Research, Elsevier, vol. 221(3), pages 533-545.
    10. Laub, Jeffrey D. & Fowler, John W. & Keha, Ahmet B., 2007. "Minimizing makespan with multiple-orders-per-job in a two-machine flowshop," European Journal of Operational Research, Elsevier, vol. 182(1), pages 63-79, October.
    11. Fehmi Tanrisever & Erhan Kutanoglu, 2008. "Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem," Annals of Operations Research, Springer, vol. 159(1), pages 5-24, March.
    12. Li, Xueping & Zhang, Kaike, 2018. "Single batch processing machine scheduling with two-dimensional bin packing constraints," International Journal of Production Economics, Elsevier, vol. 196(C), pages 113-121.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    18. 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.
    19. 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.
    20. 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.

    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:16:y:2008:i:2:d:10.1007_s10878-007-9128-7. 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.