A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
Summary: In this paper, we propose a variable block insertion heuristic (VBIH) algorithm to solve the permutation flow shop scheduling problem (PFSP). The VBIH algorithm removes a block of jobs from the current solution. It applies an insertion local search to the partial solution. Then, it inserts the block into all possible positions in the partial solution sequentially. It chooses the best one amongst those solutions from block insertion moves. Finally, again an insertion local search is applied to the complete solution. If the new solution obtained is better than the current solution, it replaces the current solution with the new one. As long as it improves, it retains the same block size. Otherwise, the block size is incremented by one and a simulated annealing-based acceptance criterion is employed to accept the new solution in order to escape from local minima. This process is repeated until the block size reaches its maximum size. To verify the computational results, mixed integer programming (MIP) and constraint programming (CP) models are developed and solved using very recent small VRF benchmark suite. Optimal solutions are found for 108 out of 240 instances. Extensive computational results on the VRF large benchmark suite show that the proposed algorithm outperforms two variants of the iterated greedy algorithm. 236 out of 240 instances of large VRF benchmark suite are further improved for the first time in this paper. Ultimately, we run Taillard's benchmark suite and compare the algorithms. In addition to the above, three instances of Taillard's benchmark suite are also further improved for the first time in this paper since 1993.
- A variable block insertion heuristic for the energy-efficient permutation flowshop scheduling with makespan criterion
- A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
- A review and classification of heuristics for permutation flow-shop scheduling with makespan objective
- A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion
- Branch-and-bound algorithm for solving blocking flowshop scheduling problems with makespan criterion
- A New Heuristic Method for the Permutation Flow Shop Scheduling Problem
- On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem
- Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
- Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm
- A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective
- A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation
- A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
- A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
- A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem
- An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
- An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects
- An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives
- Benchmarks for basic scheduling problems
- Carbon-efficient scheduling of flow shops by multi-objective optimization
- Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
- Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
- Local search methods for the flowshop scheduling problem with flowtime minimization
- New hard benchmark for flowshop scheduling problems minimising makespan
- On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem
- Optimal two- and three-stage production schedules with set-up time included
- Scatter search for minimizing weighted tardiness in a single machine scheduling with setups
- Scheduling
- Some efficient heuristic methods for the flow shop sequencing problem
- The Complexity of Flowshop and Jobshop Scheduling
- A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
- Scheduling blocking flowshops with setup times via constraint guided and accelerated local search
- Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning
- Learning to select operators in meta-heuristics: an integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem
- A variable block insertion heuristic for the energy-efficient permutation flowshop scheduling with makespan criterion
- Iterative beam search algorithms for the permutation flowshop
- An evolution strategy approach for the distributed permutation flowshop scheduling problem with sequence-dependent setup times
- New efficient heuristics for scheduling open shops with makespan minimization
- Metaheuristics with restart and learning mechanisms for the no-idle flowshop scheduling problem with makespan criterion
- A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion
- Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers
- Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm
- Improved approaches to minimize the makespan on single-machine scheduling with periodic preventive maintenance activities
- Synchronizing production and delivery in flow shops with time-of-use electricity pricing
This page was built for publication: A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004870)
