An efficient optimal solution to the two-hoist no-wait cyclic scheduling problem

作     者：Liu, JY Jiang, Y 

作者机构：Univ Loughborough Sch Business Loughborough LE11 3TU Leics England Bilkent Univ Dept Ind Engn TR-06800 Bilkent Turkey 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2005年第53卷第2期

页      面：313-327页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：TIME-WINDOW CONSTRAINTS POLYNOMIAL ALGORITHM SINGLE-HOIST LINE 

摘      要：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.