Iterated greedy algorithms for a complex parallel machine scheduling problem
From MaRDI portal
Publication:2116861
DOI10.1016/J.EJOR.2021.08.005zbMATH Open1495.90079arXiv2102.06007OpenAlexW3195128206MaRDI QIDQ2116861FDOQ2116861
Victor Abu-Marrul, Arild Hoff, Rafael Martinelli, Davi Mecler
Publication date: 18 March 2022
Published in: European Journal of Operational Research (Search for Journal in Brave)
Abstract: This paper addresses a complex parallel machine scheduling problem with jobs divided into operations and operations grouped in families. Non-anticipatory family setup times are held at the beginning of each batch, defined by the combination of one setup-time and a sequence of operations from a unique family. Other aspects are also considered in the problem, such as release dates for operations and machines, operation's sizes, and machine's eligibility and capacity. We consider item availability to define the completion times of the operations within the batches, to minimize the total weighted completion time of jobs. We developed Iterated Greedy (IG) algorithms combining destroy and repair operators with a Random Variable Neighborhood Descent (RVND) local search procedure, using four neighborhood structures to solve the problem. The best algorithm variant outperforms the current literature methods for the problem, in terms of average deviation for the best solutions and computational times, in a known benchmark set of 72 instances. New upper bounds are also provided for some instances within this set. Besides, computational experiments are conducted to evaluate the proposed methods' performance in a more challenging set of instances introduced in this work. Two IG variants using a greedy repair operator showed superior performance with more than 70% of the best solutions found uniquely by these variants. Despite the simplicity, the method using the most common destruction and repair operators presented the best results in different evaluated criteria, highlighting its potential and applicability in solving a complex machine scheduling problem.
Full work available at URL: https://arxiv.org/abs/2102.06007
Recommendations
- Iterated greedy local search methods for unrelated parallel machine scheduling
- An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
- An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives
- An iterative approach for the serial batching problem with parallel machines and job families
- Iterated greedy with random variable neighborhood descent for scheduling jobs on parallel machines with deterioration effect
Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)
Cites Work
- Optimization by Simulated Annealing
- A general heuristic for vehicle routing problems
- Heuristic methods for the identical parallel machine flowtime problem with set-up times
- Open-shop batch scheduling with identical jobs
- A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines
- Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan
- Scheduling with deadlines and loss functions
- Scheduling with centralized and decentralized batching policies in concurrent open shops
- A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
- Solving the serial batching problem in job shop manufacturing systems
- A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing
- A new dominance rule to minimize total weighted tardiness with unequal release dates.
- A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
- A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
- An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
- Tight bounds for the identical parallel machine scheduling problem
- Iterated greedy local search methods for unrelated parallel machine scheduling
- A new approximation algorithm for unrelated parallel machine scheduling with release dates
- Minimizing the sum of weighted completion times in a concurrent open shop
- A note on the complexity of the concurrent open shop problem
- Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times
- An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times
- Scheduling multi-operation jobs on a single machine
- An exact algorithm for the identical parallel machine scheduling problem.
- Heuristic and exact algorithms for the identical parallel machine scheduling problem
- The longest processing time rule for identical parallel machines revisited
- Bounds for parallel machine scheduling with predefined parts of jobs and setup time
- Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
- Matheuristics for a parallel machine scheduling problem with non-anticipatory family setup times: application in the offshore oil and gas industry
- The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications
- Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints
- An ILS heuristic for the ship scheduling problem: application in the oil industry
- Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job
- A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times
- Multi-objective open shop scheduling by considering human error and preventive maintenance
- Select and permute: an improved online framework for scheduling to minimize weighted completion time
Cited In (3)
- A reactive iterated greedy algorithm for the no-wait flowshop to minimize total tardiness
- Iterated greedy with random variable neighborhood descent for scheduling jobs on parallel machines with deterioration effect
- Scheduling identical serial-batching machines in the engine manufacturing supply chain by an integrated variable neighborhood search Algorithm
This page was built for publication: Iterated greedy algorithms for a complex parallel machine scheduling problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116861)
