无重叠区的两抓钩周期性排序问题的一个搜索求解法  

A Search Algorithm for Cyclic Scheduling of Two Hoists without Overlapping partition

作　　者：周支立[1] 汪应洛[1] 

机构地区：[1]西安交通大学管理学院,陕西西安710049

出　　处：《系统工程》2007年第4期104-109,共6页Systems Engineering

基　　金：国家自然科学基金资助项目(70371037)

摘　　要：在当今的自动化制造系统中,计算机控制的抓钩的排序直接影响系统的生产率。本文研究了产品在生产线两端装载和卸载的电镀线的周期性抓钩排序问题,目标是极小化生产周期。本文把生产线分成无重叠的两部分,并给每部分分配一个抓钩,构成一个无重叠两抓钩周期性排序问题。为了求解该问题,提出了一种基于线性规划模型和禁忌表的搜索算法。这个算法使用测试的周期长度作为控制参数以产生不同的运送顺序,对每个给定的运送顺序和抓钩分配,用线性规划模型求得子问题的最优解。在搜索中,为了避免相同序列的子问题模型的求解,采用了禁忌表。量化的示例表明所使用的方法是高效的。In today＇s highly automated manufacturing systems, computer-controlled the scheduling of hoists directly affects the throughput of these manufacturing systems. In this paper, we study the cyclic scheduling problem for electroplating lines where products are loaded into the system at one end and unloaded at the other end. The objective is to minimize the production cycle. We divide the line into two non-overlapping zones and assign a hoist for each zone, it forms a cyclic scheduling of two-hoist without overlapping partition. To solve the problem, we propose a searching algorithm which based on linear programming model. The algorithm uses trial processing times and trial cycle lengths as controlling parameters to generate different sequences of moves in the cycle. A linear programming model is then used to find the optimal schedule for each given sequence of the move and the hoist a^ignments. To avoid the solving of the same linear programming model in searching, a tabu list is used. Results of computational examples are given demonstrating the effectiveness and efficiency of the proposed algorithm.

关 键 词：抓钩 排序/调度问题 禁忌 重叠 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]