IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v83y2019icp261-274.html
   My bibliography  Save this article

Effective heuristic for large-scale unrelated parallel machines scheduling problems

Author

Listed:
  • Wang, Haibo
  • Alidaee, Bahram

Abstract

This paper is concerned with non-preemptive scheduling of large-scale unrelated parallel machines (UPM) with the objective of minimizing total weighted completion times (TWCT). We propose a sequential improvement local search algorithm using multiple-jump strategy embedded within Tabu search (TS) components for TWCT, and use a highly efficient data structure to provide a necessary and sufficient condition for local optimality of a solution. We will generate a set of large-scale test problems to evaluate the performance of proposed algorithm in term of scalability, solution quality and efficiency. The non-parametric tests of algorithm components will be used to validate the consistent performance across problem types and problem sizes in the proposed algorithm.

Suggested Citation

  • Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    • Handle: RePEc:eee:jomega:v:83:y:2019:i:c:p:261-274
    DOI: 10.1016/j.omega.2018.07.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048318302081
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2018.07.005?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. Jose Juan Carreno, 1990. "Economic Lot Scheduling for Multiple Products on Parallel Identical Processors," Management Science, INFORMS, vol. 36(3), pages 348-358, March.
    2. Biskup, Dirk & Herrmann, Jan & Gupta, Jatinder N.D., 2008. "Scheduling identical parallel machines to minimize total tardiness," International Journal of Production Economics, Elsevier, vol. 115(1), pages 134-142, September.
    3. F. Della Croce & R. Tadei & P.S. Asioli, 1999. "Scheduling a round robin tennis tournamentunder courts and players availability constraints," Annals of Operations Research, Springer, vol. 92(0), pages 349-361, January.
    4. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    5. F. Rodriguez & C. Blum & C. García-Martínez & M. Lozano, 2012. "GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times," Annals of Operations Research, Springer, vol. 201(1), pages 383-401, December.
    6. 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.
    7. Fanjul-Peyro, Luis & Ruiz, Rubén, 2010. "Iterated greedy local search methods for unrelated parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 207(1), pages 55-69, November.
    8. Cheng, T. C. E. & Sin, C. C. S., 1990. "A state-of-the-art review of parallel-machine scheduling research," European Journal of Operational Research, Elsevier, vol. 47(3), pages 271-292, August.
    9. Plateau, M.-C. & Rios-Solis, Y.A., 2010. "Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations," European Journal of Operational Research, Elsevier, vol. 201(3), pages 729-736, March.
    10. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    11. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    12. S-O Shim & Y-D Kim, 2007. "Minimizing total tardiness in an unrelated parallel-machine scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 346-354, March.
    13. Tjark Vredeveld & Cor Hurkens, 2002. "Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 175-189, May.
    14. Halil Şen & Kerem Bülbül, 2015. "A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 135-150, February.
    15. Wang, Dujuan & Yin, Yunqiang & Cheng, T.C.E., 2018. "Parallel-machine rescheduling with job unavailability and rejection," Omega, Elsevier, vol. 81(C), pages 246-260.
    16. Peter Brucker & Johann Hurink, 2000. "Solving a chemical batch scheduling problem by local search," Annals of Operations Research, Springer, vol. 96(1), pages 17-38, November.
    17. Fred Glover & Gary A. Kochenberger & Bahram Alidaee, 1998. "Adaptive Memory Tabu Search for Binary Quadratic Programs," Management Science, INFORMS, vol. 44(3), pages 336-345, March.
    18. Yin, Yunqiang & Cheng, T.C.E. & Wang, Du-Juan, 2016. "Rescheduling on identical parallel machines with machine disruptions to minimize total completion time," European Journal of Operational Research, Elsevier, vol. 252(3), pages 737-749.
    19. Zhi-Long Chen & Warren B. Powell, 1999. "Solving Parallel Machine Scheduling Problems by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 78-94, February.
    20. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    21. Fabrizio Marinelli & Maria Nenni & Antonio Sforza, 2007. "Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company," Annals of Operations Research, Springer, vol. 150(1), pages 177-192, March.
    22. Gara-Ali, Ahmed & Finke, Gerd & Espinouse, Marie-Laure, 2016. "Parallel-machine scheduling with maintenance: Praising the assignment problem," European Journal of Operational Research, Elsevier, vol. 252(1), pages 90-97.
    23. Shih-Wei Lin & Kuo-Ching Ying, 2015. "A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems," International Journal of Production Research, Taylor & Francis Journals, vol. 53(4), pages 1065-1076, February.
    24. Yin, Yunqiang & Cheng, Shuenn-Ren & Cheng, T.C.E. & Wang, Du-Juan & Wu, Chin-Chia, 2016. "Just-in-time scheduling with two competing agents on unrelated parallel machines," Omega, Elsevier, vol. 63(C), pages 41-47.
    25. Jarrah, Ahmad I. Z. & Bard, Jonathan F. & de Silva, Anura H., 1992. "A heuristic for machine scheduling at general mail facilities," European Journal of Operational Research, Elsevier, vol. 63(2), pages 192-206, December.
    26. T'kindt, V. & Billaut, J-C. & Proust, C., 2001. "Solving a bicriteria scheduling problem on unrelated parallel machines occurring in the glass bottle industry," European Journal of Operational Research, Elsevier, vol. 135(1), pages 42-49, November.
    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. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).
    2. Zhang, Zhe & Gong, Xue & Song, Xiaoling & Yin, Yong & Lev, Benjamin & Chen, Jie, 2022. "A column generation-based exact solution method for seru scheduling problems," Omega, Elsevier, vol. 108(C).
    3. Yung-Chia Chang & Kuei-Hu Chang & Ching-Ping Zheng, 2022. "Application of a Non-Dominated Sorting Genetic Algorithm to Solve a Bi-Objective Scheduling Problem Regarding Printed Circuit Boards," Mathematics, MDPI, vol. 10(13), pages 1-21, July.
    4. Bahram Alidaee & Haibo Wang & R. Bryan Kethley & Frank Landram, 2019. "A unified view of parallel machine scheduling with interdependent processing rates," Journal of Scheduling, Springer, vol. 22(5), pages 499-515, October.
    5. Wang, Haibo & Alidaee, Bahram, 2019. "The multi-floor cross-dock door assignment problem: Rising challenges for the new trend in logistics industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 30-47.
    6. Hamza Jouhari & Deming Lei & Mohammed A. A. Al-qaness & Mohamed Abd Elaziz & Ahmed A. Ewees & Osama Farouk, 2019. "Sine-Cosine Algorithm to Enhance Simulated Annealing for Unrelated Parallel Machine Scheduling with Setup Times," Mathematics, MDPI, vol. 7(11), pages 1-18, November.
    7. Yueyue Liu & Xiaoya Liao & Rui Zhang, 2019. "An Enhanced MOPSO Algorithm for Energy-Efficient Single-Machine Production Scheduling," Sustainability, MDPI, vol. 11(19), pages 1-16, September.
    8. Chen, Wenchong & Gong, Xuejian & Rahman, Humyun Fuad & Liu, Hongwei & Qi, Ershi, 2021. "Real-time order acceptance and scheduling for data-enabled permutation flow shops: Bilevel interactive optimization with nonlinear integer programming," Omega, Elsevier, vol. 105(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. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    2. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    3. F. Rodriguez & C. Blum & C. García-Martínez & M. Lozano, 2012. "GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times," Annals of Operations Research, Springer, vol. 201(1), pages 383-401, December.
    4. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    5. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    6. Teobaldo Bulhões & Ruslan Sadykov & Anand Subramanian & Eduardo Uchoa, 2020. "On the exact solution of a large class of parallel machine scheduling problems," Journal of Scheduling, Springer, vol. 23(4), pages 411-429, August.
    7. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    8. Yanıkoğlu, İhsan & Yavuz, Tonguc, 2022. "Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 301(3), pages 875-895.
    9. Wu, Xueqi & Che, Ada, 2019. "A memetic differential evolution algorithm for energy-efficient parallel machine scheduling," Omega, Elsevier, vol. 82(C), pages 155-165.
    10. Halil Şen & Kerem Bülbül, 2015. "A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 135-150, February.
    11. Zoltán Varga & Pál Simon, 2014. "Examination Of Scheduling Methods For Production Systems," Advanced Logistic systems, University of Miskolc, Department of Material Handling and Logistics, vol. 8(1), pages 111-120, December.
    12. Tao Wu & Zhe Liang & Canrong Zhang, 2018. "Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 236-258, May.
    13. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.
    14. Rabia Nessah & Chengbin Chu, 2010. "Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods," Annals of Operations Research, Springer, vol. 181(1), pages 359-375, December.
    15. Norelhouda Sekkal & Fayçal Belkaid, 0. "A multi-objective simulated annealing to solve an identical parallel machine scheduling problem with deterioration effect and resources consumption constraints," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-37.
    16. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    17. Daniel Reich & Yuhui Shi & Marina Epelman & Amy Cohn & Ellen Barnes & Kirk Arthurs & Erica Klampfl, 2016. "Scheduling Crash Tests at Ford Motor Company," Interfaces, INFORMS, vol. 46(5), pages 409-423, October.
    18. Oron, Daniel, 2021. "Two-agent scheduling problems under rejection budget constraints," Omega, Elsevier, vol. 102(C).
    19. Artigues, Christian & Lopez, Pierre & Haït, Alain, 2013. "The energy scheduling problem: Industrial case-study and constraint propagation techniques," International Journal of Production Economics, Elsevier, vol. 143(1), pages 13-23.
    20. Wenchang Luo & Rylan Chin & Alexander Cai & Guohui Lin & Bing Su & An Zhang, 2022. "A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 690-722, August.

    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:jomega:v:83:y:2019:i:c:p:261-274. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.