Metaheuristic Algorithms for Related Parallel Machines Scheduling Problem with Availability and Periodical Unavailability Constraints

Abstract

The Related Parallel Machine Scheduling Problem (R-PMSP) is a type of optimal job scheduling problem. The problem is to assign different types of jobs to different parallel machines. Every machine has a speed rate that can execute a job faster or slower than other machines. This paper focuses on an R-PMSP, with availability and periodical unavailability constraints. Some jobs can also have machine preferences. The problem with these constraints is NP-hard. This study describes three metaheuristic algorithms for solving the problem. Namely, the algorithms are Genetic Algorithm (GA), Simulated Annealing (SA), and Discrete Grey Wolf Optimizer (DGWO). This article focuses on examining the performance of the algorithms, determined by the required time, to find a suboptimal threshold. Simulated Annealing proved to be the best in terms of efficiency and time required to find the suboptimal threshold. In addition, the study describes a benchmark generator method for this problem, which guarantees to create a problem with given properties and with a given optimum.