文章基本信息

标题：Metaheuristics for optimizing unrelated parallel machines scheduling with unreliable resources to minimize makespan
本地全文：下载
作者：Husam Kaid ; Abdulrahman Al-Ahmari ; Adel Al-Shayea 等
期刊名称：Advances in Mechanical Engineering
印刷版ISSN：1687-8140
电子版ISSN：1687-8140
出版年度：2022
卷号：14
期号：5
页码：1-12
DOI：10.1177/16878132221097023
语种：English
出版社：Sage Publications Ltd.
摘要：Parallel machines scheduling problems with continuous availability of machines are NP-hardness (non-deterministic polynomial-time hardness) and have become very popular for the last decade; there is still very limited literature on this problem. The purpose of this paper is to focus on the problem of scheduling n independent jobs to be processed on m unrelated identical parallel machines with availability constraints to minimize the maximum completion time of jobs (makespan). For this NP-hard problem, a mixed-integer linear programming (MILP) model is proposed to find an optimal solution for this problem. Two metaheuristics, tabu search (TS) and simulated annealing (SA) are proposed to solve large scale problem. Moreover, the performance of the solution obtained by the proposed metaheuristics is evaluated based on a lower bound, which decreases the time required to find the optimal solution. Extensive experiments are carried out to assess the performance of all proposed metaheuristics. The computational results highlight the ability of the proposed metaheuristics to obtain optimal solutions for most of the instances compared with the solutions of the proposed MILP model and lower bounds. Moreover, SA and TS can provide good efficiency for the problem in any jobs size and any machine size, but TS provides worse CPU time as the size of jobs become large.
关键词：Tabu search;simulated annealing;scheduling;parallel machines;makespan