A Branch-and-Bound Algorithm to Minimize the Makespan in a Flowshop with Blocking

This work addresses the minimization of the makespan criterion for the flowshop problem with blocking. In this environment there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. We propose a lower b...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2005-09, Vol.138 (1), p.53-65
Main Author: Ronconi, Débora P.
Format: Article
Language:English
Subjects:
Algorithms
Branch & bound algorithms
Employment
Heuristic
Job shops
Manufacturing
Operations research
Queuing
Scheduling
Studies
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This work addresses the minimization of the makespan criterion for the flowshop problem with blocking. In this environment there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. We propose a lower bound which exploits the occurrence of blocking. A branch-and-bound algorithm that uses this lower bound is described and its efficiency is evaluated on several problems. Results of computational experiments are reported. [PUBLICATION ABSTRACT]
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-005-2444-3