@article{article_1811804, title={A new neighborhood-based VNS algorithm for unrelated parallel machine scheduling problem with sequence-dependent setup times}, journal={Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi}, volume={32}, year={2025}, DOI={10.5505/pajes.2025.05935}, author={Kılıç, Günay and Organ, Arzu}, keywords={Değişken Komşuluk Arama, Metasezgisel, Sıra Bağımlı Hazırlık Süreli İlişkisiz Paralel Makine Çizelgeleme}, abstract={Scheduling involves the allocation of tasks to machines under specific constraints and criteria. As schedules are constructed and jobs are assigned to machines, various scheduling challenges arise. This study focuses on the NP-hard Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSPSDT), where jobs have varying processing times across machines, and setup times between jobs depend on the machine. The objective is to minimize the makespan (Cmax) of the final schedule. Due to its computational complexity, exact methods are ineffective in solving UPMSPSDT efficiently, leading researchers to explore metaheuristic approaches for near-optimal solutions.
This study aims to enhance solution quality for UPMSPSDT using the Variable Neighborhood Search (VNS) algorithm, a single-solution metaheuristic. To this end, a novel neighborhood structure is introduced, inspired by the shell-changing behavior of crabs, complementing existing structures in the literature. Additionally, three different local search strategies are evaluated based on the makespan values obtained through neighborhood transitions and are applied iteratively using a local search selection strategy. Furthermore, an improved version of a greedy initial solution from the literature is proposed to generate higher-quality starting solutions. The proposed Crab-inspired Neighborhood-based VNS (CNVNS) is tested on a widely used benchmark dataset, and the results are analyzed. Findings indicate that the proposed algorithm outperforms benchmarked approaches in achieving lower Cmax values, demonstrating its effectiveness in solving UPMSPSDT.}, number={2}, publisher={Pamukkale Üniversitesi}