Two new parameter proposals for variable neighborhood descent algorithm to minimize Cmax in machine scheduling problem

Authors : Günay Kılıç, Arzu Organ

Pages : 36-46

Doi:10.56554/jtom.1515258

View : 63 | Download : 76

Publication Date : 2025-07-01

Article Type : Research Paper

Abstract :Scheduling can be defined as the assignment of jobs to machines that will be processed under certain constraints and measurements. Different scheduling problems arise when creating schedules and assigning jobs to machines. The problem of interest in this study is the Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSPST), which is classified as NP-hard. The objective of the problem is to minimize the makespan (Cmax). In UPMSPST, machines have different processing times for jobs and there are machine-dependent setup times between jobs. Exact solution methods are not sufficient for solving the UPMSPST and many metaheuristics have been proposed by researchers to find approximate solutions. The aim of this paper is to propose two new parameters for solving the UPMSPST with the Variable Neighborhood Descent (VND) algorithm, which is a single-solution metaheuristic algorithm, in order to find better solutions. The proposed parameters are tested in four different scenarios and the results of the best parameter configuration are given. The results show that the proposed new parameters are effective in improving the existing solution.
Keywords : Variable Neighborhood Descent, Metaheuristic, Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times

ORIGINAL ARTICLE URL