A polynomial algorithm for no-wait cyclic multi-hoist scheduling

Ada Che; Chengbin Chu

doi:10.1109/ICSSSM.2006.320671

A polynomial algorithm for no-wait cyclic multi-hoist scheduling

Ada Che
, Chengbin Chu

School of Management

Université de technologie de Troyes

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

This paper addresses cyclic scheduling of multiple hoists in a no-wait electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently maximizing the production throughput, for a given number of hoists. The problem is first formulated as a set of prohibited intervals for the cycle time. We then prove that the optimal cycle time is necessarily one of special values of the cycle time, and thus reduce the problem to a feasibility-checking problem for a given value of the cycle time. We show that the latter problem can be transformed to a longest path problem in a directed graph. The complete algorithm is shown to be polynomial in the number of tanks in an electroplating line.

Original language	English
Title of host publication	Proceedings - ICSSSM'06
Subtitle of host publication	2006 International Conference on Service Systems and Service Management
Publisher	IEEE Computer Society
Pages	1156-1161
Number of pages	6
ISBN (Print)	1424404517, 9781424404513
DOIs	https://doi.org/10.1109/ICSSSM.2006.320671
State	Published - 2006
Event	ICSSSM'06: 2006 International Conference on Service Systems and Service Management - Troyes, France Duration: 25 Oct 2006 → 27 Oct 2006

Publication series

Name	Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management
Volume	2

Conference

Conference	ICSSSM'06: 2006 International Conference on Service Systems and Service Management
Country/Territory	France
City	Troyes
Period	25/10/06 → 27/10/06

Keywords

Electroplating lines
Hoist scheduling problem
Multiple hoists
Polynomial algorithm

Access to Document

10.1109/ICSSSM.2006.320671

Cite this

Che, A., & Chu, C. (2006). A polynomial algorithm for no-wait cyclic multi-hoist scheduling. In Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management (pp. 1156-1161). Article 4114653 (Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management; Vol. 2). IEEE Computer Society. https://doi.org/10.1109/ICSSSM.2006.320671

@inproceedings{84ae3f855e42440e883763638999bffa,

title = "A polynomial algorithm for no-wait cyclic multi-hoist scheduling",

abstract = "This paper addresses cyclic scheduling of multiple hoists in a no-wait electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently maximizing the production throughput, for a given number of hoists. The problem is first formulated as a set of prohibited intervals for the cycle time. We then prove that the optimal cycle time is necessarily one of special values of the cycle time, and thus reduce the problem to a feasibility-checking problem for a given value of the cycle time. We show that the latter problem can be transformed to a longest path problem in a directed graph. The complete algorithm is shown to be polynomial in the number of tanks in an electroplating line.",

keywords = "Electroplating lines, Hoist scheduling problem, Multiple hoists, Polynomial algorithm",

author = "Ada Che and Chengbin Chu",

year = "2006",

doi = "10.1109/ICSSSM.2006.320671",

language = "英语",

isbn = "1424404517",

series = "Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management",

publisher = "IEEE Computer Society",

pages = "1156--1161",

booktitle = "Proceedings - ICSSSM'06",

note = "ICSSSM'06: 2006 International Conference on Service Systems and Service Management ; Conference date: 25-10-2006 Through 27-10-2006",

}

Che, A & Chu, C 2006, A polynomial algorithm for no-wait cyclic multi-hoist scheduling. in Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management., 4114653, Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management, vol. 2, IEEE Computer Society, pp. 1156-1161, ICSSSM'06: 2006 International Conference on Service Systems and Service Management, Troyes, France, 25/10/06. https://doi.org/10.1109/ICSSSM.2006.320671

A polynomial algorithm for no-wait cyclic multi-hoist scheduling. / Che, Ada; Chu, Chengbin.
Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management. IEEE Computer Society, 2006. p. 1156-1161 4114653 (Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A polynomial algorithm for no-wait cyclic multi-hoist scheduling

AU - Che, Ada

AU - Chu, Chengbin

PY - 2006

Y1 - 2006

N2 - This paper addresses cyclic scheduling of multiple hoists in a no-wait electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently maximizing the production throughput, for a given number of hoists. The problem is first formulated as a set of prohibited intervals for the cycle time. We then prove that the optimal cycle time is necessarily one of special values of the cycle time, and thus reduce the problem to a feasibility-checking problem for a given value of the cycle time. We show that the latter problem can be transformed to a longest path problem in a directed graph. The complete algorithm is shown to be polynomial in the number of tanks in an electroplating line.

AB - This paper addresses cyclic scheduling of multiple hoists in a no-wait electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently maximizing the production throughput, for a given number of hoists. The problem is first formulated as a set of prohibited intervals for the cycle time. We then prove that the optimal cycle time is necessarily one of special values of the cycle time, and thus reduce the problem to a feasibility-checking problem for a given value of the cycle time. We show that the latter problem can be transformed to a longest path problem in a directed graph. The complete algorithm is shown to be polynomial in the number of tanks in an electroplating line.

KW - Electroplating lines

KW - Hoist scheduling problem

KW - Multiple hoists

KW - Polynomial algorithm

UR - https://www.scopus.com/pages/publications/40649084896

U2 - 10.1109/ICSSSM.2006.320671

DO - 10.1109/ICSSSM.2006.320671

M3 - 会议稿件

AN - SCOPUS:40649084896

SN - 1424404517

SN - 9781424404513

T3 - Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management

SP - 1156

EP - 1161

BT - Proceedings - ICSSSM'06

PB - IEEE Computer Society

T2 - ICSSSM'06: 2006 International Conference on Service Systems and Service Management

Y2 - 25 October 2006 through 27 October 2006

ER -

A polynomial algorithm for no-wait cyclic multi-hoist scheduling

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this