Search tree based approaches for parallel machine scheduling

This article compares two branching schemes for the parallel machine scheduling problem with release dates and tails. Both branching schemes can be used for either complete or incomplete search tree based algorithms. In particular, our study aims to prove the robustness of each of them for several s...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2008-04, Vol.35 (4), p.1127-1137
Main Authors: Néron, Emmanuel, Tercinet, Fabrice, Sourd, Francis
Format: Article
Language:English
Subjects:
Applied sciences
Branch & bound algorithms
Comparative analysis
Computational Complexity
Computer Science
Exact sciences and technology
Inventory control, production control. Distribution
Job shops
Makespan
Operational research and scientific management
Operational research. Management science
Operations Research
Parallel machine scheduling
Parallel processing
Production scheduling
Release dates
Scheduling, sequencing
Search tree
Studies
Tails
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 article compares two branching schemes for the parallel machine scheduling problem with release dates and tails. Both branching schemes can be used for either complete or incomplete search tree based algorithms. In particular, our study aims to prove the robustness of each of them for several search methods. We experimentally compare the efficiency of the two branching schemes when they are used in a branch-and-bound (BnB) method, in a limited discrepancy search, in a branch-and-greed (BnG) method or in a beam search (BS).
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2006.07.008