Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion
A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2020-09-01
|
| Series: | International Journal of Applied Mathematics and Computer Science |
| Subjects: | |
| Online Access: | https://doi.org/10.34768/amcs-2020-0042 |
| _version_ | 1818720259307208704 |
|---|---|
| author | Wang Wen Chen Xin Musial Jedrzej Blazewicz Jacek |
| author_facet | Wang Wen Chen Xin Musial Jedrzej Blazewicz Jacek |
| author_sort | Wang Wen |
| collection | DOAJ |
| description | A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search (TS) and a genetic algorithm (GA), both of which are equipped with the techniques of initialization, iteration, as well as termination. The performances of the designed algorithms are verified through computational experiments, where we show that the GA can produce better solutions but with a higher time consumption. Moreover, we also analyze the influence of problem parameters on the performances of these meta-heuristics. |
| first_indexed | 2024-12-17T20:20:00Z |
| format | Article |
| id | doaj.art-61ab35eb66ec4e59963cbad83212846a |
| institution | Directory Open Access Journal |
| issn | 2083-8492 |
| language | English |
| last_indexed | 2024-12-17T20:20:00Z |
| publishDate | 2020-09-01 |
| publisher | Sciendo |
| record_format | Article |
| series | International Journal of Applied Mathematics and Computer Science |
| spelling | doaj.art-61ab35eb66ec4e59963cbad83212846a2022-12-21T21:33:58ZengSciendoInternational Journal of Applied Mathematics and Computer Science2083-84922020-09-0130357358410.34768/amcs-2020-0042amcs-2020-0042Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work CriterionWang Wen0Chen Xin1Musial Jedrzej2Blazewicz Jacek3School of Electronics and Information Engineering, Liaoning University of Technology, Shiying 169, 121001Jinzhou, ChinaSchool of Electronics and Information Engineering, Liaoning University of Technology, Shiying 169, 121001Jinzhou, ChinaInstitute of Computing Science, Poznań University of Technology, ul. Piotrowo 3a, 60-965Poznań, PolandInstitute of Computing Science, Poznań University of Technology, ul. Piotrowo 3a, 60-965Poznań, PolandA scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search (TS) and a genetic algorithm (GA), both of which are equipped with the techniques of initialization, iteration, as well as termination. The performances of the designed algorithms are verified through computational experiments, where we show that the GA can produce better solutions but with a higher time consumption. Moreover, we also analyze the influence of problem parameters on the performances of these meta-heuristics.https://doi.org/10.34768/amcs-2020-0042late work minimizationunrelated machinestabu searchgenetic algorithm |
| spellingShingle | Wang Wen Chen Xin Musial Jedrzej Blazewicz Jacek Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion International Journal of Applied Mathematics and Computer Science late work minimization unrelated machines tabu search genetic algorithm |
| title | Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion |
| title_full | Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion |
| title_fullStr | Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion |
| title_full_unstemmed | Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion |
| title_short | Two Meta–Heuristic Algorithms for Scheduling on Unrelated Machines with the Late Work Criterion |
| title_sort | two meta heuristic algorithms for scheduling on unrelated machines with the late work criterion |
| topic | late work minimization unrelated machines tabu search genetic algorithm |
| url | https://doi.org/10.34768/amcs-2020-0042 |
| work_keys_str_mv | AT wangwen twometaheuristicalgorithmsforschedulingonunrelatedmachineswiththelateworkcriterion AT chenxin twometaheuristicalgorithmsforschedulingonunrelatedmachineswiththelateworkcriterion AT musialjedrzej twometaheuristicalgorithmsforschedulingonunrelatedmachineswiththelateworkcriterion AT blazewiczjacek twometaheuristicalgorithmsforschedulingonunrelatedmachineswiththelateworkcriterion |