Weighted earliness/tardiness parallel machine scheduling problem with a common due date
| Autor: | Marco Schutten, Engin Topan, Oğuzhan Ahmet Arık |
|---|---|
| Přispěvatelé: | Digital Society Institute, Industrial Engineering & Business Information Systems |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Mathematical optimization
Parallel machine Computer science business.industry Heuristic Scheduling Tardiness Earliness General Engineering Computer Science Applications Artificial bee colony algorithm V-shaped Common due date Artificial Intelligence Genetic algorithm Simulated annealing Local search (optimization) business Heuristics Metaheuristic |
| Zdroj: | Expert systems with applications, 187:115916. Elsevier |
| ISSN: | 0957-4174 |
| Popis: | © 2021 Elsevier LtdThis 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect