IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v334y2018icp254-268.html
   My bibliography  Save this article

A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capacities and arbitrary job sizes

Author

Listed:
  • Zhou, Shengchao
  • Xie, Jianhui
  • Du, Ni
  • Pang, Yan

Abstract

A batch processing machine (BPM) can simultaneously process several jobs and has wide applications in various industrial environments. This paper studies the problem of minimizing makespan on unrelated parallel BPMs with non-identical job sizes and arbitrary release times. In the environment of unrelated machines, each machine has a processing speed for each job. The unrelated BPM problem is the most general case of parallel BPM problems and is closer to actual production conditions. The problem under study is NP-hard. We present two lower bounds for the problem. Then a genetic algorithm based on random-keys encoding is proposed to solve the problem. The performance of the proposed algorithm is compared with a commercial solver (ILOG CPLEX) and two meta-heuristics published in the literature: a recent iterated greedy algorithm and a particle swarm optimization algorithm. Computational experiments show that the proposed algorithm produces better solutions compared to the other methods. The quality of the proposed lower bounds is evaluated as well.

Suggested Citation

  • Zhou, Shengchao & Xie, Jianhui & Du, Ni & Pang, Yan, 2018. "A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capacities and arbitrary job sizes," Applied Mathematics and Computation, Elsevier, vol. 334(C), pages 254-268.
    • Handle: RePEc:eee:apmaco:v:334:y:2018:i:c:p:254-268
    DOI: 10.1016/j.amc.2018.04.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300318303424
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2018.04.024?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. 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.
    3. Colin R. Reeves, 1997. "Feature Article---Genetic Algorithms for the Operations Researcher," INFORMS Journal on Computing, INFORMS, vol. 9(3), pages 231-250, August.
    4. 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.
    5. Xiaotie Deng & Haodi Feng & Guojun Li & Benyun Shi, 2005. "A PTAS for Semiconductor Burn-in Scheduling," Journal of Combinatorial Optimization, Springer, vol. 9(1), pages 5-17, February.
    6. Sung, C. S. & Choung, Y. I., 2000. "Minimizing makespan on a single burn-in oven in semiconductor manufacturing," European Journal of Operational Research, Elsevier, vol. 120(3), pages 559-574, February.
    7. Jia, Zhao-hong & Li, Kai & Leung, Joseph Y.-T., 2015. "Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities," International Journal of Production Economics, Elsevier, vol. 169(C), pages 1-10.
    8. A H Kashan & B Karimi, 2008. "Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: An ant colony framework," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1269-1280, September.
    9. 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.
    10. Chung-Lun Li & Chung-Yee Lee, 1997. "Scheduling with agreeable release times and due dates on a batch processing machine," European Journal of Operational Research, Elsevier, vol. 96(3), pages 564-569, February.
    11. 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.
    12. Zhou, Shengchao & Liu, Ming & Chen, Huaping & Li, Xueping, 2016. "An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes," International Journal of Production Economics, Elsevier, vol. 179(C), pages 1-11.
    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. Jae Won Jang & Yong Jae Kim & Byung Soo Kim, 2022. "A Three-Stage ACO-Based Algorithm for Parallel Batch Loading and Scheduling Problem with Batch Deterioration and Rate-Modifying Activities," Mathematics, MDPI, vol. 10(4), pages 1-26, February.
    2. Liman Feng & Guo Chen & Shengchao Zhou & Xiaojun Zhou & Mingzhou Jin, 2024. "An Energy-Efficient Unrelated Parallel Machine Scheduling Problem with Batch Processing and Time-of-Use Electricity Prices," Mathematics, MDPI, vol. 12(3), pages 1-14, January.
    3. Zhang, Han & Li, Kai & Jia, Zhao-hong & Chu, Chengbin, 2023. "Minimizing total completion time on non-identical parallel batch machines with arbitrary release times using ant colony optimization," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1024-1046.
    4. Wei Jiang & Yilan Shen & Lingxuan Liu & Xiancong Zhao & Leyuan Shi, 2022. "A new method for a class of parallel batch machine scheduling problem," Flexible Services and Manufacturing Journal, Springer, vol. 34(2), pages 518-550, June.
    5. Lotfi Hidri & Ali Alqahtani & Achraf Gazdar & Belgacem Ben Youssef, 2021. "Green Scheduling of Identical Parallel Machines with Release Date, Delivery Time and No-Idle Machine Constraints," Sustainability, MDPI, vol. 13(16), pages 1-30, August.
    6. Husseinzadeh Kashan, Ali & Ozturk, Onur, 2022. "Improved MILP formulation equipped with valid inequalities for scheduling a batch processing machine with non-identical job sizes," Omega, Elsevier, vol. 112(C).

    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. 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.
    2. Zhou, Shengchao & Liu, Ming & Chen, Huaping & Li, Xueping, 2016. "An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes," International Journal of Production Economics, Elsevier, vol. 179(C), pages 1-11.
    3. Zhang, Han & Li, Kai & Jia, Zhao-hong & Chu, Chengbin, 2023. "Minimizing total completion time on non-identical parallel batch machines with arbitrary release times using ant colony optimization," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1024-1046.
    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. 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.
    6. 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.
    7. Min Kong & Xinbao Liu & Jun Pei & Panos M. Pardalos & Nenad Mladenovic, 2020. "Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines," Journal of Global Optimization, Springer, vol. 78(4), pages 693-715, December.
    8. Xu, Rui & Chen, Huaping & Li, Xueping, 2013. "A bi-objective scheduling problem on batch machines via a Pareto-based ant colony system," International Journal of Production Economics, Elsevier, vol. 145(1), pages 371-386.
    9. Wang, Jun-Qiang & Fan, Guo-Qiang & Zhang, Yingqian & Zhang, Cheng-Wu & Leung, Joseph Y.-T., 2017. "Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes," European Journal of Operational Research, Elsevier, vol. 258(2), pages 478-490.
    10. 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.
    11. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    12. A H Kashan & B Karimi, 2008. "Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: An ant colony framework," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1269-1280, September.
    13. Ozturk, Onur, 2020. "A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 432-443.
    14. Jolai, Fariborz, 2005. "Minimizing number of tardy jobs on a batch processing machine with incompatible job families," European Journal of Operational Research, Elsevier, vol. 162(1), pages 184-190, April.
    15. Wang, Jun-Qiang & Leung, Joseph Y.-T., 2014. "Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan," International Journal of Production Economics, Elsevier, vol. 156(C), pages 325-331.
    16. Husseinzadeh Kashan, Ali & Ozturk, Onur, 2022. "Improved MILP formulation equipped with valid inequalities for scheduling a batch processing machine with non-identical job sizes," Omega, Elsevier, vol. 112(C).
    17. Li, Shuguang, 2017. "Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities," European Journal of Operational Research, Elsevier, vol. 263(3), pages 815-826.
    18. 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.
    19. 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.
    20. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).

    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:apmaco:v:334:y:2018:i:c:p:254-268. 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: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.