Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times
This study considers a scheduling problem for a flow shop with urgent jobs and limited waiting times. The urgent jobs and limited waiting times are major considerations for scheduling in semiconductor manufacturing systems. The objective function is to minimize a weighted sum of total tardiness of u...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/11/323 |
| _version_ | 1797511542656204800 |
|---|---|
| author | BongJoo Jeong Jun-Hee Han Ju-Yong Lee |
| author_facet | BongJoo Jeong Jun-Hee Han Ju-Yong Lee |
| author_sort | BongJoo Jeong |
| collection | DOAJ |
| description | This study considers a scheduling problem for a flow shop with urgent jobs and limited waiting times. The urgent jobs and limited waiting times are major considerations for scheduling in semiconductor manufacturing systems. The objective function is to minimize a weighted sum of total tardiness of urgent jobs and the makespan of normal jobs. This problem is formulated in mixed integer programming (MIP). By using a commercial optimization solver, the MIP can be used to find an optimal solution. However, because this problem is proved to be NP-hard, solving to optimality requires a significantly long computation time for a practical size problem. Therefore, this study adopts metaheuristic algorithms to obtain a good solution quickly. To complete this, two metaheuristic algorithms (an iterated greedy algorithm and a simulated annealing algorithm) are proposed, and a series of computational experiments were performed to examine the effectiveness and efficiency of the proposed algorithms. |
| first_indexed | 2024-03-10T05:46:47Z |
| format | Article |
| id | doaj.art-1ad67c6128af4c4b8d80aa3f94064284 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T05:46:47Z |
| publishDate | 2021-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-1ad67c6128af4c4b8d80aa3f940642842023-11-22T22:04:53ZengMDPI AGAlgorithms1999-48932021-11-01141132310.3390/a14110323Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting TimesBongJoo Jeong0Jun-Hee Han1Ju-Yong Lee2Department of Business Administration, Kongju National University, Kongju-si 32588, KoreaDepartment of Industrial and Management Engineering, Dong-A University, Busan 49315, KoreaDivision of Business Administration & Accounting, Kangwon National University, Chuncheon-si 24341, KoreaThis study considers a scheduling problem for a flow shop with urgent jobs and limited waiting times. The urgent jobs and limited waiting times are major considerations for scheduling in semiconductor manufacturing systems. The objective function is to minimize a weighted sum of total tardiness of urgent jobs and the makespan of normal jobs. This problem is formulated in mixed integer programming (MIP). By using a commercial optimization solver, the MIP can be used to find an optimal solution. However, because this problem is proved to be NP-hard, solving to optimality requires a significantly long computation time for a practical size problem. Therefore, this study adopts metaheuristic algorithms to obtain a good solution quickly. To complete this, two metaheuristic algorithms (an iterated greedy algorithm and a simulated annealing algorithm) are proposed, and a series of computational experiments were performed to examine the effectiveness and efficiency of the proposed algorithms.https://www.mdpi.com/1999-4893/14/11/323schedulingflow shopurgent jobslimited waiting timesmetaheuristic |
| spellingShingle | BongJoo Jeong Jun-Hee Han Ju-Yong Lee Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times Algorithms scheduling flow shop urgent jobs limited waiting times metaheuristic |
| title | Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times |
| title_full | Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times |
| title_fullStr | Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times |
| title_full_unstemmed | Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times |
| title_short | Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times |
| title_sort | metaheuristics for a flow shop scheduling problem with urgent jobs and limited waiting times |
| topic | scheduling flow shop urgent jobs limited waiting times metaheuristic |
| url | https://www.mdpi.com/1999-4893/14/11/323 |
| work_keys_str_mv | AT bongjoojeong metaheuristicsforaflowshopschedulingproblemwithurgentjobsandlimitedwaitingtimes AT junheehan metaheuristicsforaflowshopschedulingproblemwithurgentjobsandlimitedwaitingtimes AT juyonglee metaheuristicsforaflowshopschedulingproblemwithurgentjobsandlimitedwaitingtimes |