Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem
This paper considers two kinds of stochastic reentrant job shop scheduling problems (SRJSSP), i.e., the SRJSSP with the maximum tardiness criterion and the SRJSSP with the makespan criterion. Owing to the NP-complete complexity of the considered RJSSPs, an effective differential evolutionary algorit...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2022/9924163 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832567769939312640 |
|---|---|
| author | Rong Hu Xing Wu Bin Qian Jianlin Mao Huaiping Jin |
| author_facet | Rong Hu Xing Wu Bin Qian Jianlin Mao Huaiping Jin |
| author_sort | Rong Hu |
| collection | DOAJ |
| description | This paper considers two kinds of stochastic reentrant job shop scheduling problems (SRJSSP), i.e., the SRJSSP with the maximum tardiness criterion and the SRJSSP with the makespan criterion. Owing to the NP-complete complexity of the considered RJSSPs, an effective differential evolutionary algorithm (DEA) combined with two uncertainty handling techniques, namely, DEA_UHT, is proposed to address these problems. Firstly, to reasonably control the computation cost, the optimal computing budget allocation technique (OCBAT) is applied for allocating limited computation budgets to assure reliable evaluation and identification for excellent solutions or individuals, and the hypothesis test technique (HTT) is added to execute a statistical comparison to reduce some unnecessary repeated evaluation. Secondly, a reentrant-largest-order-value rule is designed to convert the DEA’s individual (i.e., a continuous vector) to the SRJSSP’s solution (i.e., an operation permutation). Thirdly, a conventional active decoding scheme for the job shop scheduling problem is extended to decode the solution for obtaining the criterion value. Fourthly, an Insert-based exploitation strategy and an Interchange-based exploration strategy are devised to enhance DEA’s exploitation ability and exploration ability, respectively. Finally, the test results and comparisons manifest the effectiveness and robustness of the proposed DEA_UHT. |
| format | Article |
| id | doaj-art-fdc1773c57614cab972a49f66d3b52bd |
| institution | Kabale University |
| issn | 1099-0526 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-fdc1773c57614cab972a49f66d3b52bd2025-02-03T01:00:46ZengWileyComplexity1099-05262022-01-01202210.1155/2022/9924163Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling ProblemRong Hu0Xing Wu1Bin Qian2Jianlin Mao3Huaiping Jin4Faculty of Mechanical & Electrical EngineeringFaculty of Mechanical & Electrical EngineeringFaculty of Information Engineering and AutomationFaculty of Information Engineering and AutomationFaculty of Information Engineering and AutomationThis paper considers two kinds of stochastic reentrant job shop scheduling problems (SRJSSP), i.e., the SRJSSP with the maximum tardiness criterion and the SRJSSP with the makespan criterion. Owing to the NP-complete complexity of the considered RJSSPs, an effective differential evolutionary algorithm (DEA) combined with two uncertainty handling techniques, namely, DEA_UHT, is proposed to address these problems. Firstly, to reasonably control the computation cost, the optimal computing budget allocation technique (OCBAT) is applied for allocating limited computation budgets to assure reliable evaluation and identification for excellent solutions or individuals, and the hypothesis test technique (HTT) is added to execute a statistical comparison to reduce some unnecessary repeated evaluation. Secondly, a reentrant-largest-order-value rule is designed to convert the DEA’s individual (i.e., a continuous vector) to the SRJSSP’s solution (i.e., an operation permutation). Thirdly, a conventional active decoding scheme for the job shop scheduling problem is extended to decode the solution for obtaining the criterion value. Fourthly, an Insert-based exploitation strategy and an Interchange-based exploration strategy are devised to enhance DEA’s exploitation ability and exploration ability, respectively. Finally, the test results and comparisons manifest the effectiveness and robustness of the proposed DEA_UHT.http://dx.doi.org/10.1155/2022/9924163 |
| spellingShingle | Rong Hu Xing Wu Bin Qian Jianlin Mao Huaiping Jin Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem Complexity |
| title | Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem |
| title_full | Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem |
| title_fullStr | Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem |
| title_full_unstemmed | Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem |
| title_short | Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem |
| title_sort | differential evolution algorithm combined with uncertainty handling techniques for stochastic reentrant job shop scheduling problem |
| url | http://dx.doi.org/10.1155/2022/9924163 |
| work_keys_str_mv | AT ronghu differentialevolutionalgorithmcombinedwithuncertaintyhandlingtechniquesforstochasticreentrantjobshopschedulingproblem AT xingwu differentialevolutionalgorithmcombinedwithuncertaintyhandlingtechniquesforstochasticreentrantjobshopschedulingproblem AT binqian differentialevolutionalgorithmcombinedwithuncertaintyhandlingtechniquesforstochasticreentrantjobshopschedulingproblem AT jianlinmao differentialevolutionalgorithmcombinedwithuncertaintyhandlingtechniquesforstochasticreentrantjobshopschedulingproblem AT huaipingjin differentialevolutionalgorithmcombinedwithuncertaintyhandlingtechniquesforstochasticreentrantjobshopschedulingproblem |