A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
type: Item
instance of: scholarly article
title: A variable block insertion heuristic for the blocking flowshop scheduling problem with total flowtime criterion
zbMATH Open document ID: 1461.90058
author: Mehmet Fatih Tasgetiren
author: Damla Kizilay
author: Kai-Zhou Gao
author: Quanke Pan
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: In this paper, we present a variable block insertion heuristic (VBIH) algorithm to solve the blocking flowshop scheduling problem with the total flowtime criterion. In the VBIH algorithm, we define a minimum and a maximum block size. After constructing the initial sequence, the VBIH algorithm starts with a minimum block size being equal to one. It removes the block from the current sequence and inserts it into the partial sequence sequentially with a predetermined move size. The sequence, which is obtained after several block moves, goes under a variable local search (VLS), which is based on traditional insertion and swap neighborhood structures. If the new sequence obtained after the VLS local search is better than the current sequence, it replaces the current sequence. As long as it improves, it keeps the same block size. However, if it does not improve, the block size is incremented by one and a simulated annealing-type of acceptance criterion is used to accept the current sequence. This process is repeated until the block size reaches at the maximum block size. Furthermore, we present a novel constructive heuristic, which is based on the profile fitting heuristic from the literature. The proposed constructive heuristic is able to further improve the best known solutions for some larger instances in a few seconds. Parameters of the constructive heuristic and the VBIH algorithm are determined through a design of experiment approach. Extensive computational results on the Taillard's well-known benchmark suite show that the proposed VBIH algorithm outperforms the discrete artificial bee colony algorithm, which is one of the most efficient algorithms recently in the literature. Ultimately, 52 out of the 150 best known solutions are further improved with substantial margins.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7042380
zbMATH Keywords: meta-heuristics
zbMATH Keywords: blocking flowshop
zbMATH Keywords: block insertion heuristic
zbMATH Keywords: variable local search
zbMATH Keywords: constructive heuristics
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a9040071
OpenAlex ID: W2539426768
cites work: Handbook on Scheduling
cites work: Sequencing of jobs in some production system
cites work: A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Q3768703
cites work: Sequencing in an Assembly Line with Blocking to Minimize Cycle Time
cites work: Flowshop sequencing problems with limited buffer storage
cites work: Lower bounding schemes for flowshops with blocking in-process
cites work: Minimizing Cycle Time in a Blocking Flowshop
cites work: Constructive and composite heuristic solutions to the \(P\|\sum C_i\) scheduling problem
cites work: A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking
cites work: Benchmarks for basic scheduling problems
cites work: An effective hybrid genetic algorithm for flow shop scheduling with limited buffers
cites work: An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers
cites work: An effective hybrid DE-based algorithm for flow shop scheduling with limited buffers
cites work: A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems
cites work: A three-phase algorithm for flowshop scheduling with blocking to minimize makespan
cites work: Optimizing blocking flow shop scheduling problem with total completion time criterion
cites work: A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine
cites work: Iterated local search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness
cites work: Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion
cites work: Variable neighborhood search
cites work: A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem
cites work: A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem
cites work: Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem
cites work: Q5437767
cites work: A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem
cites work: A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times
cites work: A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion
cites work: Design and Analysis of Experiments, Second Edition
cites work: Local search methods for the flowshop scheduling problem with flowtime minimization
DOI: 10.3390/A9040071
description: scientific article; zbMATH DE number 7042380