Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates

Tao Ren, Yan Zhang, Shuenn-Ren Cheng, Chin-Chia Wu, Meng Zhang, Bo-yu Chang, Xin-yue Wang and Peng Zhao
Additional contact information
Tao Ren: College of Software, Northeastern University, Shenyang 110819, China
Yan Zhang: College of Software, Northeastern University, Shenyang 110819, China
Shuenn-Ren Cheng: Department of Business Administration, Cheng Shiu University, Kaohsiung 83347, Taiwan
Chin-Chia Wu: Department of Statistics, Feng Chia University, Taichung 40724, Taiwan
Meng Zhang: College of Software, Northeastern University, Shenyang 110819, China
Bo-yu Chang: College of Software, Northeastern University, Shenyang 110819, China
Xin-yue Wang: College of Software, Northeastern University, Shenyang 110819, China
Peng Zhao: College of Software, Northeastern University, Shenyang 110819, China

Mathematics, 2020, vol. 8, issue 8, 1-25

Abstract: 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.

Keywords: jobshop scheduling; release date; heuristic algorithm; discrete differential evolution (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/8/1221/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/8/1221/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:8:p:1221-:d:389696

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().