The tool switching problem revisited

Y. Crama; L.S. Moonen; F.C.R. Spieksma; E. Talloen

doi:10.1016/j.ejor.2006.07.028

The tool switching problem revisited

Y. Crama, L.S. Moonen, F.C.R. Spieksma, E. Talloen

Research output: Contribution to journal › Article › Academic › peer-review

22 Citations (Scopus)

Abstract

In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly
NP-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem.

Original language	English
Pages (from-to)	952-957
Journal	European Journal of Operational Research
Volume	182
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2006.07.028
Publication status	Published - 16 Oct 2007
Externally published	Yes

Keywords

complexity theory
flexible manufacturing systems

Access to Document

10.1016/j.ejor.2006.07.028

Cite this

@article{c82146ff54a04091baab00a55947e723,

title = "The tool switching problem revisited",

abstract = "In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly NP-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem.",

keywords = "complexity theory, flexible manufacturing systems",

author = "Y. Crama and L.S. Moonen and F.C.R. Spieksma and E. Talloen",

year = "2007",

month = oct,

day = "16",

doi = "10.1016/j.ejor.2006.07.028",

language = "English",

volume = "182",

pages = "952--957",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - The tool switching problem revisited

AU - Crama, Y.

AU - Moonen, L.S.

AU - Spieksma, F.C.R.

AU - Talloen, E.

PY - 2007/10/16

Y1 - 2007/10/16

N2 - In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly NP-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem.

AB - In this note we study the tool switching problem with non-uniform tool sizes. More specifically, we consider the problem where the job sequence is given as part of the input. We show that the resulting tooling problem is strongly NP-complete, even in case of unit loading and unloading costs. On the other hand, if the capacity of the tool magazine is also given as part of the input, we show that the problem is solvable in polynomial time. These results settle the complexity of a relevant variant of the tool switching problem.

KW - complexity theory

KW - flexible manufacturing systems

U2 - 10.1016/j.ejor.2006.07.028

DO - 10.1016/j.ejor.2006.07.028

M3 - Article

SN - 0377-2217

VL - 182

SP - 952

EP - 957

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

The tool switching problem revisited

Abstract

Keywords

Access to Document

Fingerprint

Cite this