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

Ada Che, Chengbin Chu

科研成果: 书/报告/会议事项章节会议稿件同行评审

3 引用 (Scopus)

摘要

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.

源语言英语
主期刊名Proceedings - ICSSSM'06
主期刊副标题2006 International Conference on Service Systems and Service Management
出版商IEEE Computer Society
1156-1161
页数6
ISBN(印刷版)1424404517, 9781424404513
DOI
出版状态已出版 - 2006
活动ICSSSM'06: 2006 International Conference on Service Systems and Service Management - Troyes, 法国
期限: 25 10月 200627 10月 2006

出版系列

姓名Proceedings - ICSSSM'06: 2006 International Conference on Service Systems and Service Management
2

会议

会议ICSSSM'06: 2006 International Conference on Service Systems and Service Management
国家/地区法国
Troyes
时期25/10/0627/10/06

指纹

探究 'A polynomial algorithm for no-wait cyclic multi-hoist scheduling' 的科研主题。它们共同构成独一无二的指纹。

引用此