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

2 4( 160)　　　　 　 　系　统　工　程 Vol. 2 , No. 4 20074　　　　　　　　　 　 　 　 Systems Engineering Apr. , 2007 : 1001-4098(2007) 04-0104-06 周支立,汪应洛 ( , 　710049) 　: 在当今的自动化制造系统中,计算机控制的抓钩的排序直接影响系统的生 率。本文研究了 品在生 线两端装载和卸载的电镀线的周期性抓钩排序问题,目标是极小化生 周期。本文把生 线分成无重叠的 两部分,并给每部分分配一个抓钩,构成一个无重叠两抓钩周期性排序问题。为了求解该问题,提出了一种基 于线性规划模型和禁忌表的搜索算法。这 个算法使用测试的周期长度作为控制参数以 生不同的运送顺序, 对每 个给定的运送顺序和抓钩分配 ,用线性规划模型求得子问题的最优解。在搜索中,为了避免相同序列的子 问题模型的求解,采用了禁忌表。量化的示例表明所使用的方法是高效的。 : 抓钩;排序 /调度问题;禁忌;重叠 : T P278　　　: A 　　 , ,,。 。 ,, ,。 1 。, 。 。 ,、、 , 。, , 。 ,“ 。 ”, ,, 。 ,, 1　 　　 , ,。 20, [1 ] , ( N P-complete) 。 。 Phillips [2] 、 。 : 2006-09-30;: 2007-01-30 : ( : , ,;, ,,。 4　　　　 　 　,: 10 [3- 6] 。 Baptiste 。 [7] 。 ,, Lei 2　问题描述 , : n+ 2 [8] 。Varnier 。: 0, 1, 2,… , n , n+ 1, [9] 。Leung