A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
type: Item
instance of: scholarly article
title: A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
zbMATH Open document ID: 1461.90050
author: Damla Kizilay
author: Mehmet Fatih Tasgetiren
author: Liang Gao
author: Quanke Pan
published in: Algorithms
publication date: 2020-10-07T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7257166
zbMATH Keywords: heuristic optimization
zbMATH Keywords: block insertion heuristic
zbMATH Keywords: flow shop scheduling
zbMATH Keywords: iterated greedy algorithm
zbMATH Keywords: constraint programming
zbMATH Keywords: mixed integer programming
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a12050100
OpenAlex ID: W2945158825
cites work: A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation
cites work: Scheduling
cites work: The Complexity of Flowshop and Jobshop Scheduling
cites work: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem
cites work: An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
cites work: An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives
cites work: On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem
cites work: New hard benchmark for flowshop scheduling problems minimising makespan
cites work: An iterated greedy heuristic for no-wait flow shops with sequence dependent setup times, learning and forgetting effects
cites work: Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
cites work: A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem
cites work: Carbon-efficient scheduling of flow shops by multi-objective optimization
cites work: Local search methods for the flowshop scheduling problem with flowtime minimization
cites work: Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
cites work: Scatter search for minimizing weighted tardiness in a single machine scheduling with setups
cites work: A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
cites work: Some efficient heuristic methods for the flow shop sequencing problem
cites work: Optimal two- and three-stage production schedules with set-up time included
cites work: Benchmarks for basic scheduling problems
Wikidata QID: Q127891877
DOI: 10.3390/A12050100
Recommended article: A variable block insertion heuristic for the energy-efficient permutation flowshop scheduling with makespan criterion
Recommended article: A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
Recommended article: A review and classification of heuristics for permutation flow-shop scheduling with makespan objective
Recommended article: A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion
Recommended article: Branch-and-bound algorithm for solving blocking flowshop scheduling problems with makespan criterion
Recommended article: A New Heuristic Method for the Permutation Flow Shop Scheduling Problem
Recommended article: On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem
Recommended article: Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
Recommended article: Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm
Recommended article: A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective
description: scientific article; zbMATH DE number 7257166