A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis
Job shop scheduling problem (JSSP) has drawn a lot of attention as it is one of the vital combinational optimization problems in manufacturing systems. In this paper, a differential-based harmony search (DHS) algorithm with variable neighborhood search (VNS) is proposed for solving JSSP with the obj...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8506369/ |
| _version_ | 1819163143561019392 |
|---|---|
| author | Fuqing Zhao Shuo Qin Guoqiang Yang Weimin Ma Chuck Zhang Houbin Song |
| author_facet | Fuqing Zhao Shuo Qin Guoqiang Yang Weimin Ma Chuck Zhang Houbin Song |
| author_sort | Fuqing Zhao |
| collection | DOAJ |
| description | Job shop scheduling problem (JSSP) has drawn a lot of attention as it is one of the vital combinational optimization problems in manufacturing systems. In this paper, a differential-based harmony search (DHS) algorithm with variable neighborhood search (VNS) is proposed for solving JSSP with the objective of minimized makespan. Since the standard harmony search algorithm is constructed for global optimization problems, the smallest position value is introduced to map a harmony vector to an active schedule. The active decoding scheme is employed to improve the search efficiency of DHS. In the pitch-adjustment process, the best individual of the current harmony memory is employed to accelerate the convergence speed. After the pitch-adjustment process, the differential-based enhanced mechanism is designed to maintain the diversity of the population. The modified VNS, which is based on the blocks on the critical path, is embedded into DHS to search for a better solution around the current harmony vector. Besides, the runtime of DHS is analyzed according to the level-based theorem. Compared with various HSbased algorithms and other state-of-the-art algorithms on a set of typical benchmark instances, the DHS is superior to the compared algorithms in terms of solution quality, convergence speed, and stability. The DHS lays a solid foundation for solving optimization problems of expert and intelligent systems. |
| first_indexed | 2024-12-22T17:39:27Z |
| format | Article |
| id | doaj.art-b66b13dc04d64cb5bb6edd11925a35b8 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T17:39:27Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-b66b13dc04d64cb5bb6edd11925a35b82022-12-21T18:18:26ZengIEEEIEEE Access2169-35362018-01-016763137633010.1109/ACCESS.2018.28777918506369A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime AnalysisFuqing Zhao0https://orcid.org/0000-0002-7336-9699Shuo Qin1Guoqiang Yang2Weimin Ma3Chuck Zhang4Houbin Song5School of Computer and Communication Technology, Lanzhou University of Technology, Lanzhou, ChinaSchool of Computer and Communication Technology, Lanzhou University of Technology, Lanzhou, ChinaSchool of Computer and Communication Technology, Lanzhou University of Technology, Lanzhou, ChinaSchool of Economics and Management, Tongji University, Shanghai, ChinaH. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USASchool of Computer and Communication Technology, Lanzhou University of Technology, Lanzhou, ChinaJob shop scheduling problem (JSSP) has drawn a lot of attention as it is one of the vital combinational optimization problems in manufacturing systems. In this paper, a differential-based harmony search (DHS) algorithm with variable neighborhood search (VNS) is proposed for solving JSSP with the objective of minimized makespan. Since the standard harmony search algorithm is constructed for global optimization problems, the smallest position value is introduced to map a harmony vector to an active schedule. The active decoding scheme is employed to improve the search efficiency of DHS. In the pitch-adjustment process, the best individual of the current harmony memory is employed to accelerate the convergence speed. After the pitch-adjustment process, the differential-based enhanced mechanism is designed to maintain the diversity of the population. The modified VNS, which is based on the blocks on the critical path, is embedded into DHS to search for a better solution around the current harmony vector. Besides, the runtime of DHS is analyzed according to the level-based theorem. Compared with various HSbased algorithms and other state-of-the-art algorithms on a set of typical benchmark instances, the DHS is superior to the compared algorithms in terms of solution quality, convergence speed, and stability. The DHS lays a solid foundation for solving optimization problems of expert and intelligent systems.https://ieeexplore.ieee.org/document/8506369/Job shop scheduling problemharmony searchvariable neighborhood searchruntime analysisdifferential-based enhanced mechanism |
| spellingShingle | Fuqing Zhao Shuo Qin Guoqiang Yang Weimin Ma Chuck Zhang Houbin Song A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis IEEE Access Job shop scheduling problem harmony search variable neighborhood search runtime analysis differential-based enhanced mechanism |
| title | A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis |
| title_full | A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis |
| title_fullStr | A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis |
| title_full_unstemmed | A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis |
| title_short | A Differential-Based Harmony Search Algorithm With Variable Neighborhood Search for Job Shop Scheduling Problem and Its Runtime Analysis |
| title_sort | differential based harmony search algorithm with variable neighborhood search for job shop scheduling problem and its runtime analysis |
| topic | Job shop scheduling problem harmony search variable neighborhood search runtime analysis differential-based enhanced mechanism |
| url | https://ieeexplore.ieee.org/document/8506369/ |
| work_keys_str_mv | AT fuqingzhao adifferentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT shuoqin adifferentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT guoqiangyang adifferentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT weiminma adifferentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT chuckzhang adifferentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT houbinsong adifferentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT fuqingzhao differentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT shuoqin differentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT guoqiangyang differentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT weiminma differentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT chuckzhang differentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis AT houbinsong differentialbasedharmonysearchalgorithmwithvariableneighborhoodsearchforjobshopschedulingproblemanditsruntimeanalysis |