An efficient optimal solution to the two-hoist no-wait cyclic scheduling problem
成果类型：
Article
署名作者：
Liu, JY; Jiang, Y
署名单位：
Loughborough University; Ihsan Dogramaci Bilkent University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0167
发表日期：
2005
页码：
313-327
关键词：
摘要：
Hoist scheduling is a typical problem in the operation of electroplating systems. The cyclic scheduling policy is widely used in these systems in industry. Research on hoist scheduling has focused on the cyclic problem to minimize the cycle length. Most previous studies consider the single-hoist case. In practice, however, more than one hoist is often used in an electroplating line. This paper addresses the two-hoist, no-wait cyclic scheduling problem, in which the tank-processing times are constants and, upon completion of processing in a tank, the parts have to be moved to the next tank immediately. Based on the analysis of the problem properties, a polynomial algorithm is developed to obtain an optimal schedule. This algorithm first identifies a set of thresholds, which are special values of the cycle length, so that the feasibility property may change only at these thresholds. Feasibility checking is then carried out on each individual threshold in ascending order. The first feasible threshold found will be the optimal cycle length, and the corresponding feasible schedule is an optimal hoist schedule.