Exact Approaches to Late Work Scheduling on Unrelated Machines
We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2023-06-01
|
| Series: | International Journal of Applied Mathematics and Computer Science |
| Subjects: | |
| Online Access: | https://doi.org/10.34768/amcs-2023-0021 |
| _version_ | 1797794981247713280 |
|---|---|
| author | Liu Xinbo Wang Wen Chen Xin Sterna Malgorzata Blazewicz Jacek |
| author_facet | Liu Xinbo Wang Wen Chen Xin Sterna Malgorzata Blazewicz Jacek |
| author_sort | Liu Xinbo |
| collection | DOAJ |
| description | We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments. |
| first_indexed | 2024-03-13T03:10:55Z |
| format | Article |
| id | doaj.art-84ebf6ebcf36436692b0d901676e42e6 |
| institution | Directory Open Access Journal |
| issn | 2083-8492 |
| language | English |
| last_indexed | 2024-03-13T03:10:55Z |
| publishDate | 2023-06-01 |
| publisher | Sciendo |
| record_format | Article |
| series | International Journal of Applied Mathematics and Computer Science |
| spelling | doaj.art-84ebf6ebcf36436692b0d901676e42e62023-06-26T10:48:37ZengSciendoInternational Journal of Applied Mathematics and Computer Science2083-84922023-06-0133228529510.34768/amcs-2023-0021Exact Approaches to Late Work Scheduling on Unrelated MachinesLiu Xinbo0Wang Wen1Chen Xin2Sterna Malgorzata3Blazewicz Jacek41SolBridge International School of BusinessWoosong University, Uam-ro 128, Daejeon 34613, Republic of Korea2School of Electronics and Information Engineering Liaoning, University of Technology Shiying, 169, Jinzhou 121001, China2School of Electronics and Information Engineering Liaoning, University of Technology Shiying, 169, Jinzhou 121001, China3Institute of Computing Science, Poznan University of Technologyul. Piotrowo 2, 60-965Poznan, Poland3Institute of Computing Science, Poznan University of Technologyul. Piotrowo 2, 60-965Poznan, PolandWe consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments.https://doi.org/10.34768/amcs-2023-0021late work schedulingunrelated machinesmathematical modelbranch-and-bound algorithmdynamic programming |
| spellingShingle | Liu Xinbo Wang Wen Chen Xin Sterna Malgorzata Blazewicz Jacek Exact Approaches to Late Work Scheduling on Unrelated Machines International Journal of Applied Mathematics and Computer Science late work scheduling unrelated machines mathematical model branch-and-bound algorithm dynamic programming |
| title | Exact Approaches to Late Work Scheduling on Unrelated Machines |
| title_full | Exact Approaches to Late Work Scheduling on Unrelated Machines |
| title_fullStr | Exact Approaches to Late Work Scheduling on Unrelated Machines |
| title_full_unstemmed | Exact Approaches to Late Work Scheduling on Unrelated Machines |
| title_short | Exact Approaches to Late Work Scheduling on Unrelated Machines |
| title_sort | exact approaches to late work scheduling on unrelated machines |
| topic | late work scheduling unrelated machines mathematical model branch-and-bound algorithm dynamic programming |
| url | https://doi.org/10.34768/amcs-2023-0021 |
| work_keys_str_mv | AT liuxinbo exactapproachestolateworkschedulingonunrelatedmachines AT wangwen exactapproachestolateworkschedulingonunrelatedmachines AT chenxin exactapproachestolateworkschedulingonunrelatedmachines AT sternamalgorzata exactapproachestolateworkschedulingonunrelatedmachines AT blazewiczjacek exactapproachestolateworkschedulingonunrelatedmachines |