有重叠的两抓钩周期性排序问题的启发式算法

Heuristic Method for Two-Hoist Cyclic Scheduling with Overlapping

抓钩排序问题不同于古典的排序问题 ,只有一个抓钩和一种产品 ,它仍然被证明为NP难题 .对于有重叠区域的两抓钩周期性排序问题 ,迄今尚无法用数学模型直接求解 .为了寻找出好的排序 ,提出了一种启发式算法以求解有重叠两抓钩周期性排序问题 .该方法把问题分解成相应序列的子问题 ,并对每个序列建立和求解一个整体问题的线性规划模型 .在序列空间中 ,通过寻找好的序列以得到最佳的排序 .量化的示例表明所使用的方法是高效的 .

Computer controlled hoists are widely used for conveying materal in production.The scheduling problem for one and two hoists is different, the latter involves overlapping and cannot be solved directly by means of mathmatical modelling.A heuristic method is proposed by modelling subproblems associated with sequencing and linear programming.For each sequence, the whole problem is built and solved. Best scheduling is obtained by searching good sequence in the sequence space.A numerical example is solved to validate the proposed method.