Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
An important element in the integration of the fourth industrial revolution is the development of efficient algorithms to deal with dynamic scheduling problems. In dynamic scheduling, jobs can be admitted during the execution of a given schedule, which necessitates appropriately planned rescheduling...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/3/74 |
| _version_ | 1818455229502324736 |
|---|---|
| author | Tamer F. Abdelmaguid |
| author_facet | Tamer F. Abdelmaguid |
| author_sort | Tamer F. Abdelmaguid |
| collection | DOAJ |
| description | An important element in the integration of the fourth industrial revolution is the development of efficient algorithms to deal with dynamic scheduling problems. In dynamic scheduling, jobs can be admitted during the execution of a given schedule, which necessitates appropriately planned rescheduling decisions for maintaining a high level of performance. In this paper, a dynamic case of the multiprocessor open shop scheduling problem is addressed. This problem appears in different contexts, particularly those involving diagnostic operations in maintenance and health care industries. Two objectives are considered simultaneously—the minimization of the makespan and the minimization of the mean weighted flow time. The former objective aims to sustain efficient utilization of the available resources, while the latter objective helps in maintaining a high customer satisfaction level. An exact algorithm is presented for generating optimal Pareto front solutions. Despite the fact that the studied problem is NP-hard for both objectives, the presented algorithm can be used to solve small instances. This is demonstrated through computational experiments on a testbed of 30 randomly generated instances. The presented algorithm can also be used to generate approximate Pareto front solutions in case computational time needed to find proven optimal solutions for generated sub-problems is found to be excessive. Furthermore, computational results are used to investigate the characteristics of the optimal Pareto front of the studied problem. Accordingly, some insights for future metaheuristic developments are drawn. |
| first_indexed | 2024-12-14T22:07:27Z |
| format | Article |
| id | doaj.art-3254d23ecbe54255873a2ad804a3466e |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-14T22:07:27Z |
| publishDate | 2020-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-3254d23ecbe54255873a2ad804a3466e2022-12-21T22:45:50ZengMDPI AGAlgorithms1999-48932020-03-011337410.3390/a13030074a13030074Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact AlgorithmTamer F. Abdelmaguid0Department of Mechanical Design and Production, Faculty of Engineering, Cairo University, Giza 12613, EgyptAn important element in the integration of the fourth industrial revolution is the development of efficient algorithms to deal with dynamic scheduling problems. In dynamic scheduling, jobs can be admitted during the execution of a given schedule, which necessitates appropriately planned rescheduling decisions for maintaining a high level of performance. In this paper, a dynamic case of the multiprocessor open shop scheduling problem is addressed. This problem appears in different contexts, particularly those involving diagnostic operations in maintenance and health care industries. Two objectives are considered simultaneously—the minimization of the makespan and the minimization of the mean weighted flow time. The former objective aims to sustain efficient utilization of the available resources, while the latter objective helps in maintaining a high customer satisfaction level. An exact algorithm is presented for generating optimal Pareto front solutions. Despite the fact that the studied problem is NP-hard for both objectives, the presented algorithm can be used to solve small instances. This is demonstrated through computational experiments on a testbed of 30 randomly generated instances. The presented algorithm can also be used to generate approximate Pareto front solutions in case computational time needed to find proven optimal solutions for generated sub-problems is found to be excessive. Furthermore, computational results are used to investigate the characteristics of the optimal Pareto front of the studied problem. Accordingly, some insights for future metaheuristic developments are drawn.https://www.mdpi.com/1999-4893/13/3/74industry 4.0dynamic schedulingmulti-processor open shop schedulingmulti-objective optimizationexact algorithms |
| spellingShingle | Tamer F. Abdelmaguid Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm Algorithms industry 4.0 dynamic scheduling multi-processor open shop scheduling multi-objective optimization exact algorithms |
| title | Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm |
| title_full | Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm |
| title_fullStr | Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm |
| title_full_unstemmed | Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm |
| title_short | Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm |
| title_sort | bi objective dynamic multiprocessor open shop scheduling an exact algorithm |
| topic | industry 4.0 dynamic scheduling multi-processor open shop scheduling multi-objective optimization exact algorithms |
| url | https://www.mdpi.com/1999-4893/13/3/74 |
| work_keys_str_mv | AT tamerfabdelmaguid biobjectivedynamicmultiprocessoropenshopschedulinganexactalgorithm |