Scheduling with tool changes to minimize total completion time: Basic results and SPT performance

We consider a single machine sequencing problem subject to tool wear, where the objective is to minimize the total completion time. We briefly describe the problem and discuss its properties, complexity and solution. Mainly, however, we focus on the performance of the SPT list-scheduling heuristic....

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2004-09, Vol.157 (3), p.784-790
Main Authors: Akturk, M.Selim, Ghosh, Jay B., Gunes, Evrim D.
Format: Article
Language:English
Subjects:
Performance analysis
Scheduling
SPT list-scheduling
Tool change
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:We consider a single machine sequencing problem subject to tool wear, where the objective is to minimize the total completion time. We briefly describe the problem and discuss its properties, complexity and solution. Mainly, however, we focus on the performance of the SPT list-scheduling heuristic. We provide theoretical worst-case bounds on SPT performance and also demonstrate its empirical behavior.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(03)00232-7