Improved Q‐learning algorithm for solving permutation flow shop scheduling problems
Abstract Generally, scheduling problems refer to allocation of available shared resources and the sorting of production tasks, in order to satisfy the specified performance target within a certain time. The fundamental scheduling problem is that all jobs need to be processed on the same route, which...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-03-01
|
| Series: | IET Collaborative Intelligent Manufacturing |
| Subjects: | |
| Online Access: | https://doi.org/10.1049/cim2.12042 |
| _version_ | 1817998379941101568 |
|---|---|
| author | Zimiao He Kunlan Wang Hanxiao Li Hong Song Zhongjie Lin Kaizhou Gao Ali Sadollah |
| author_facet | Zimiao He Kunlan Wang Hanxiao Li Hong Song Zhongjie Lin Kaizhou Gao Ali Sadollah |
| author_sort | Zimiao He |
| collection | DOAJ |
| description | Abstract Generally, scheduling problems refer to allocation of available shared resources and the sorting of production tasks, in order to satisfy the specified performance target within a certain time. The fundamental scheduling problem is that all jobs need to be processed on the same route, which is called flow shop scheduling problems (FSSP). The goal of FSSP, proven as an NP‐hard problem, is to find a job sequence that minimizes the makespan. In this paper, an improved Q‐learning algorithm is proposed for solving the FSSP. Firstly, a problem model based on the basic Q‐learning algorithm is constructed. The makespan is used as the feedback signal, and the process of environmental state change is defined as the process of job selection. Q‐learning gives the expected utility of taking a given action in a given state. Afterwards, combined with the NEH heuristic, the algorithm efficiency is enhanced by changing the job inserting mode. In order to validate the proposed method, several simulation experiments are carried out on a set of test problems having different scales. The obtained optimization results of the proposed algorithm are compared to the standard Q‐learning algorithm and a hybrid algorithm. The discussion and analysis show that the proposed algorithm performs better than the others in solving the permutation FSSP. As a future direction, in order to shorten the running time, further improvements will be studied to increase the performance of the proposed algorithm and make it applicable and efficient for solving multi‐objective optimization problems. |
| first_indexed | 2024-04-14T02:52:25Z |
| format | Article |
| id | doaj.art-657f57d1e3b8437c8ff6353414a89000 |
| institution | Directory Open Access Journal |
| issn | 2516-8398 |
| language | English |
| last_indexed | 2024-04-14T02:52:25Z |
| publishDate | 2022-03-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Collaborative Intelligent Manufacturing |
| spelling | doaj.art-657f57d1e3b8437c8ff6353414a890002022-12-22T02:16:15ZengWileyIET Collaborative Intelligent Manufacturing2516-83982022-03-0141354410.1049/cim2.12042Improved Q‐learning algorithm for solving permutation flow shop scheduling problemsZimiao He0Kunlan Wang1Hanxiao Li2Hong Song3Zhongjie Lin4Kaizhou Gao5Ali Sadollah6School of Computer Liaocheng University Liaocheng ChinaIntegrate Media Center of Zhu Cheng Weifang ChinaSchool of Computer Liaocheng University Liaocheng ChinaInstitute of Systems Engineering, Macau University of Science and Technology Macau ChinaInstitute of Systems Engineering, Macau University of Science and Technology Macau ChinaSchool of Computer Liaocheng University Liaocheng ChinaDepartment of Mechanical Engineering University of Science and Culture Tehran IranAbstract Generally, scheduling problems refer to allocation of available shared resources and the sorting of production tasks, in order to satisfy the specified performance target within a certain time. The fundamental scheduling problem is that all jobs need to be processed on the same route, which is called flow shop scheduling problems (FSSP). The goal of FSSP, proven as an NP‐hard problem, is to find a job sequence that minimizes the makespan. In this paper, an improved Q‐learning algorithm is proposed for solving the FSSP. Firstly, a problem model based on the basic Q‐learning algorithm is constructed. The makespan is used as the feedback signal, and the process of environmental state change is defined as the process of job selection. Q‐learning gives the expected utility of taking a given action in a given state. Afterwards, combined with the NEH heuristic, the algorithm efficiency is enhanced by changing the job inserting mode. In order to validate the proposed method, several simulation experiments are carried out on a set of test problems having different scales. The obtained optimization results of the proposed algorithm are compared to the standard Q‐learning algorithm and a hybrid algorithm. The discussion and analysis show that the proposed algorithm performs better than the others in solving the permutation FSSP. As a future direction, in order to shorten the running time, further improvements will be studied to increase the performance of the proposed algorithm and make it applicable and efficient for solving multi‐objective optimization problems.https://doi.org/10.1049/cim2.12042optimisationjob shop schedulingcomputational complexityresource allocation |
| spellingShingle | Zimiao He Kunlan Wang Hanxiao Li Hong Song Zhongjie Lin Kaizhou Gao Ali Sadollah Improved Q‐learning algorithm for solving permutation flow shop scheduling problems IET Collaborative Intelligent Manufacturing optimisation job shop scheduling computational complexity resource allocation |
| title | Improved Q‐learning algorithm for solving permutation flow shop scheduling problems |
| title_full | Improved Q‐learning algorithm for solving permutation flow shop scheduling problems |
| title_fullStr | Improved Q‐learning algorithm for solving permutation flow shop scheduling problems |
| title_full_unstemmed | Improved Q‐learning algorithm for solving permutation flow shop scheduling problems |
| title_short | Improved Q‐learning algorithm for solving permutation flow shop scheduling problems |
| title_sort | improved q learning algorithm for solving permutation flow shop scheduling problems |
| topic | optimisation job shop scheduling computational complexity resource allocation |
| url | https://doi.org/10.1049/cim2.12042 |
| work_keys_str_mv | AT zimiaohe improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems AT kunlanwang improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems AT hanxiaoli improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems AT hongsong improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems AT zhongjielin improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems AT kaizhougao improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems AT alisadollah improvedqlearningalgorithmforsolvingpermutationflowshopschedulingproblems |