Weighted earliness/tardiness parallel machine scheduling problem with a common due date

Basit Öğe Kaydı
dc.authoridSchutten, Marco/0000-0001-5924-223X
dc.authoridArik, Oguzhan Ahmet/0000-0002-7088-2104
dc.contributor.authorArık, Oğuzhan Ahmet
dc.contributor.authorSchutten, Marco
dc.contributor.authorTopan, Engin
dc.date.accessioned2025-02-24T17:18:43Z
dc.date.available2025-02-24T17:18:43Z
dc.date.issued2022
dc.departmentFakülteler, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü
dc.description.abstractThis paper investigates an unrelated parallel machine scheduling problem with a restrictive common due date. The objective is to minimize the total sum of earliness/tardiness costs. Using some properties of the problem such as V-Shaped property, optimizing start times of machines, and no idle time between successive jobs, we propose effective construction-based heuristics and local search algorithms for the problem. Using variants of the shortest and longest processing time dispatching rules and job assignment patterns, we propose four different construction algorithms to have a balanced number of jobs or the workload per machine. We construct four deterministic and one stochastic solution improvement heuristic approaches using swap and reinsertion local search mechanisms. In the proposed reinsertion-based local search mechanism, the V-shaped property of each machine is used effectively to determine the proper positions in which the removed job is inserted. After both swap and reinsertion operators, a V-Shaped property preserving mechanism takes place to preserve the V-Shaped property of each machine. We also use an LP formulation in our proposed solution approaches to determine the optimum start times of machines for a given schedule. We compare our proposed heuristics against four metaheuristics, namely simulated annealing, genetic algorithm, artificial bee colony algorithm, and fast ruin and recreate algorithm. A simple lower bound for the optimal objective function value is proposed to show the efficiency of our proposed heuristics. We test our heuristics also in an identical machine environment. The experimental study reveals that the construction and the improvement heuristic methods including swap and reinsertion outperform metaheuristics and other heuristics in solution quality for both identical and unrelated machine environments.
dc.identifier.doi10.1016/j.eswa.2021.115916
dc.identifier.issn0957-4174
dc.identifier.issn1873-6793
dc.identifier.scopus2-s2.0-85115611564
dc.identifier.scopusqualityQ1
dc.identifier.urihttps://doi.org/10.1016/j.eswa.2021.115916
dc.identifier.urihttps://hdl.handle.net/20.500.14440/818
dc.identifier.volume187
dc.identifier.wosWOS:000706436500006
dc.identifier.wosqualityQ1
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherPergamon-Elsevier Science Ltd
dc.relation.ispartofExpert Systems With Applications
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WOS_20250201
dc.subjectParallel machine
dc.subjectCommon due date
dc.subjectEarliness
dc.subjectTardiness
dc.subjectHeuristic
dc.subjectV-shaped
dc.titleWeighted earliness/tardiness parallel machine scheduling problem with a common due date
dc.typeArticle

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Mühendislik Fakültesi Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu