Iterated greedy algorithms for a complex parallel machine scheduling problem
From MaRDI portal
Publication:2116861
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.
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
Cites work
- A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
- A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines
- A general heuristic for vehicle routing problems
- A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing
- A new approximation algorithm for unrelated parallel machine scheduling with release dates
- A new dominance rule to minimize total weighted tardiness with unequal release dates.
- A note on the complexity of the concurrent open shop problem
- A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
- A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
- A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times
- An ILS heuristic for the ship scheduling problem: application in the oil industry
- An exact algorithm for the identical parallel machine scheduling problem.
- An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times
- An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
- Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints
- Bounds for parallel machine scheduling with predefined parts of jobs and setup time
- Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times
- Heuristic and exact algorithms for the identical parallel machine scheduling problem
- Heuristic methods for the identical parallel machine flowtime problem with set-up times
- Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job
- Iterated greedy local search methods for unrelated parallel machine scheduling
- Matheuristics for a parallel machine scheduling problem with non-anticipatory family setup times: application in the offshore oil and gas industry
- Minimizing the sum of weighted completion times in a concurrent open shop
- Open-shop batch scheduling with identical jobs
- Optimization by simulated annealing
- Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time
- Retracted article: Multi-objective open shop scheduling by considering human error and preventive maintenance
- Scheduling multi-operation jobs on a single machine
- Scheduling with centralized and decentralized batching policies in concurrent open shops
- Scheduling with deadlines and loss functions
- Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan
- Solving the serial batching problem in job shop manufacturing systems
- The longest processing time rule for identical parallel machines revisited
- The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications
- Tight bounds for the identical parallel machine scheduling problem
Cited in
(6)- An iterative approach for the serial batching problem with parallel machines and job families
- A reactive iterated greedy algorithm for the no-wait flowshop to minimize total tardiness
- An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
- Iterated greedy local search methods for unrelated parallel machine scheduling
- 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)
