Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates
Manufacturing industry reflects a country’s productivity level and occupies an important share in the national economy of developed countries in the world. Jobshop scheduling (JSS) model originates from modern manufacturing, in which a number of tasks are executed individually on a series of process...
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-07-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/8/1221 |
| _version_ | 1797561352079802368 |
|---|---|
| author | Tao Ren Yan Zhang Shuenn-Ren Cheng Chin-Chia Wu Meng Zhang Bo-yu Chang Xin-yue Wang Peng Zhao |
| author_facet | Tao Ren Yan Zhang Shuenn-Ren Cheng Chin-Chia Wu Meng Zhang Bo-yu Chang Xin-yue Wang Peng Zhao |
| author_sort | Tao Ren |
| collection | DOAJ |
| description | Manufacturing industry reflects a country’s productivity level and occupies an important share in the national economy of developed countries in the world. Jobshop scheduling (JSS) model originates from modern manufacturing, in which a number of tasks are executed individually on a series of processors following their preset processing routes. This study addresses a JSS problem with the criterion of minimizing total quadratic completion time (TQCT), where each task is available at its own release date. Constructive heuristic and meta-heuristic algorithms are introduced to handle different scale instances as the problem is NP-hard. Given that the shortest-processing-time (SPT)-based heuristic and dense scheduling rule are effective for the TQCT criterion and the JSS problem, respectively, an innovative heuristic combining SPT and dense scheduling rule is put forward to provide feasible solutions for large-scale instances. A preemptive single-machine-based lower bound is designed to estimate the optimal schedule and reveal the performance of the heuristic. Differential evolution algorithm is a global search algorithm on the basis of population, which has the advantages of simple structure, strong robustness, fast convergence, and easy implementation. Therefore, a hybrid discrete differential evolution (HDDE) algorithm is presented to obtain near-optimal solutions for medium-scale instances, where multi-point insertion and a local search scheme enhance the quality of final solutions. The superiority of the HDDE algorithm is highlighted by contrast experiments with population-based meta-heuristics, i.e., ant colony optimization (ACO), particle swarm optimization (PSO) and genetic algorithm (GA). Average gaps 45.62, 63.38 and 188.46 between HDDE with ACO, PSO and GA, respectively, are demonstrated by the numerical results with benchmark data, which reveals the domination of the proposed HDDE algorithm. |
| first_indexed | 2024-03-10T18:12:44Z |
| format | Article |
| id | doaj.art-1db45d131915400c948f884b8f7f827d |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T18:12:44Z |
| publishDate | 2020-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-1db45d131915400c948f884b8f7f827d2023-11-20T07:55:04ZengMDPI AGMathematics2227-73902020-07-0188122110.3390/math8081221Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release DatesTao Ren0Yan Zhang1Shuenn-Ren Cheng2Chin-Chia Wu3Meng Zhang4Bo-yu Chang5Xin-yue Wang6Peng Zhao7College of Software, Northeastern University, Shenyang 110819, ChinaCollege of Software, Northeastern University, Shenyang 110819, ChinaDepartment of Business Administration, Cheng Shiu University, Kaohsiung 83347, TaiwanDepartment of Statistics, Feng Chia University, Taichung 40724, TaiwanCollege of Software, Northeastern University, Shenyang 110819, ChinaCollege of Software, Northeastern University, Shenyang 110819, ChinaCollege of Software, Northeastern University, Shenyang 110819, ChinaCollege of Software, Northeastern University, Shenyang 110819, ChinaManufacturing industry reflects a country’s productivity level and occupies an important share in the national economy of developed countries in the world. Jobshop scheduling (JSS) model originates from modern manufacturing, in which a number of tasks are executed individually on a series of processors following their preset processing routes. This study addresses a JSS problem with the criterion of minimizing total quadratic completion time (TQCT), where each task is available at its own release date. Constructive heuristic and meta-heuristic algorithms are introduced to handle different scale instances as the problem is NP-hard. Given that the shortest-processing-time (SPT)-based heuristic and dense scheduling rule are effective for the TQCT criterion and the JSS problem, respectively, an innovative heuristic combining SPT and dense scheduling rule is put forward to provide feasible solutions for large-scale instances. A preemptive single-machine-based lower bound is designed to estimate the optimal schedule and reveal the performance of the heuristic. Differential evolution algorithm is a global search algorithm on the basis of population, which has the advantages of simple structure, strong robustness, fast convergence, and easy implementation. Therefore, a hybrid discrete differential evolution (HDDE) algorithm is presented to obtain near-optimal solutions for medium-scale instances, where multi-point insertion and a local search scheme enhance the quality of final solutions. The superiority of the HDDE algorithm is highlighted by contrast experiments with population-based meta-heuristics, i.e., ant colony optimization (ACO), particle swarm optimization (PSO) and genetic algorithm (GA). Average gaps 45.62, 63.38 and 188.46 between HDDE with ACO, PSO and GA, respectively, are demonstrated by the numerical results with benchmark data, which reveals the domination of the proposed HDDE algorithm.https://www.mdpi.com/2227-7390/8/8/1221jobshop schedulingrelease dateheuristic algorithmdiscrete differential evolution |
| spellingShingle | Tao Ren Yan Zhang Shuenn-Ren Cheng Chin-Chia Wu Meng Zhang Bo-yu Chang Xin-yue Wang Peng Zhao Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates Mathematics jobshop scheduling release date heuristic algorithm discrete differential evolution |
| title | Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates |
| title_full | Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates |
| title_fullStr | Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates |
| title_full_unstemmed | Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates |
| title_short | Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates |
| title_sort | effective heuristic algorithms solving the jobshop scheduling problem with release dates |
| topic | jobshop scheduling release date heuristic algorithm discrete differential evolution |
| url | https://www.mdpi.com/2227-7390/8/8/1221 |
| work_keys_str_mv | AT taoren effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT yanzhang effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT shuennrencheng effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT chinchiawu effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT mengzhang effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT boyuchang effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT xinyuewang effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates AT pengzhao effectiveheuristicalgorithmssolvingthejobshopschedulingproblemwithreleasedates |