A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times
This paper addresses the flexible job shop scheduling problem with sequence-dependent set-up times and job lag times (FJSP-SDST-LT), which characteristics are important in modern manufacturing systems. We first present a mathematical model with the objective to minimize the makespan. Then a hybrid a...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9478852/ |
| _version_ | 1818354532141236224 |
|---|---|
| author | Yilun Wang Qianwen Zhu |
| author_facet | Yilun Wang Qianwen Zhu |
| author_sort | Yilun Wang |
| collection | DOAJ |
| description | This paper addresses the flexible job shop scheduling problem with sequence-dependent set-up times and job lag times (FJSP-SDST-LT), which characteristics are important in modern manufacturing systems. We first present a mathematical model with the objective to minimize the makespan. Then a hybrid algorithm (HGA-TS) which combines genetic algorithm (GA) and tabu search (TS) is proposed to solve the FJSP-SDST-LT. The GA performs powerful global search by genetic operators and serves as exploration, while based on the specific structure of SDST and LT, the TS is able to perform an effective local search by relocating operations and serves as exploitation. Therefore, the proposed HGA-TS integrates good searching ability with strong diversifying ability. In order to solve the FJSP-SDST-LT effectively, we adopt effective encoding and decoding methods, genetic operators in GA, and four neighborhood structures in TS. We conduct computational experiments on two classes of instances generated from two classic data sets and the results show the great performance of HGA-TS in solving FJSP-SDST-LT. |
| first_indexed | 2024-12-13T19:26:55Z |
| format | Article |
| id | doaj.art-e832161b8f0a4142b243f9d68c35d1b1 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-13T19:26:55Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-e832161b8f0a4142b243f9d68c35d1b12022-12-21T23:34:01ZengIEEEIEEE Access2169-35362021-01-01910486410487310.1109/ACCESS.2021.30960079478852A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag TimesYilun Wang0https://orcid.org/0000-0002-0623-2473Qianwen Zhu1https://orcid.org/0000-0001-8983-1991School of Management and Engineering, Nanjing University, Nanjing, ChinaSchool of Management and Engineering, Nanjing University, Nanjing, ChinaThis paper addresses the flexible job shop scheduling problem with sequence-dependent set-up times and job lag times (FJSP-SDST-LT), which characteristics are important in modern manufacturing systems. We first present a mathematical model with the objective to minimize the makespan. Then a hybrid algorithm (HGA-TS) which combines genetic algorithm (GA) and tabu search (TS) is proposed to solve the FJSP-SDST-LT. The GA performs powerful global search by genetic operators and serves as exploration, while based on the specific structure of SDST and LT, the TS is able to perform an effective local search by relocating operations and serves as exploitation. Therefore, the proposed HGA-TS integrates good searching ability with strong diversifying ability. In order to solve the FJSP-SDST-LT effectively, we adopt effective encoding and decoding methods, genetic operators in GA, and four neighborhood structures in TS. We conduct computational experiments on two classes of instances generated from two classic data sets and the results show the great performance of HGA-TS in solving FJSP-SDST-LT.https://ieeexplore.ieee.org/document/9478852/Flexible job shop schedulinggenetic algorithmhybrid algorithmjob lag timessequence-dependent setup timestabu search |
| spellingShingle | Yilun Wang Qianwen Zhu A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times IEEE Access Flexible job shop scheduling genetic algorithm hybrid algorithm job lag times sequence-dependent setup times tabu search |
| title | A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times |
| title_full | A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times |
| title_fullStr | A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times |
| title_full_unstemmed | A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times |
| title_short | A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times |
| title_sort | hybrid genetic algorithm for flexible job shop scheduling problem with sequence dependent setup times and job lag times |
| topic | Flexible job shop scheduling genetic algorithm hybrid algorithm job lag times sequence-dependent setup times tabu search |
| url | https://ieeexplore.ieee.org/document/9478852/ |
| work_keys_str_mv | AT yilunwang ahybridgeneticalgorithmforflexiblejobshopschedulingproblemwithsequencedependentsetuptimesandjoblagtimes AT qianwenzhu ahybridgeneticalgorithmforflexiblejobshopschedulingproblemwithsequencedependentsetuptimesandjoblagtimes AT yilunwang hybridgeneticalgorithmforflexiblejobshopschedulingproblemwithsequencedependentsetuptimesandjoblagtimes AT qianwenzhu hybridgeneticalgorithmforflexiblejobshopschedulingproblemwithsequencedependentsetuptimesandjoblagtimes |