物件空间搬运与时间集成吊机调度问题理论研究

The program takes the production, storage and retrieval processes of iron and steel enterprise for background, does the theoretical research on object space handling and time integrated crane scheduling problem. Compared with most of the existing crane scheduling problems, several special characteristics such as object with heat loss during its handling process, more performing times for the same object by crane, random and dynamic crane operation, the coordination of crane and other transport for handling objects. To solve the following key problems: 1) formulating for the object space handling and time integrated crane scheduling; 2) abstracting the features of crane scheduling, analyzing properties, demonstrating complexity; 3) constructing approximation algorithms for all problems above; 4) performance theoretical analysis of these proposed algorithms. From algorithm complexity, easy-solving and hard-solving points of view, we give theoretical research for these problems. Based on the complexity analysis, for the easy-solving problem, we present the optimal polynomial time algorithm, for the general case of the hard-solving problem, we construct effective heuristic approximation algorithm, and we further analyze and evaluate the effectiveness of the algorithm by using （asymptotic） worst case analysis, average case analysis and computational experiments. The research does not enrich the existing crane scheduling theory, but also extent crane scheduling problem to the more general case, which is helpful to improve utilization ratio of crane, decrease the operation and logistic cost, and enhance the competitiveness of enterprises.

本项目以钢铁企业生产和存取过程为背景，对物件空间搬运与时间集成的吊机调度问题进行理论研究。与国际上现有的吊机调度问题相比，其主要特征在于：物件被搬运过程存在热量损失；同一物件需要吊机进行反复多次操作；吊机操作具有随机性和动态性；吊机与其他运输工具相互衔接搬运物件等。拟解决以下关键问题：1)物件空间搬运与时间集成吊机调度建模；2)基于调度特征提取、性质分析、复杂性证明；3)基于以上各问题的近似算法构造；4)对算法性能进行理论分析。针对以上各调度，对于问题的可解情况，给出多项式时间最优算法。对于难解的问题，构造近似策略或有效的启发式算法，进一步通过理论分析如：(渐近)最坏情况分析、平均情况分析和数值计算实验等证明算法的性能。课题的研究不但丰富了现有吊机调度理论，而且使得吊机调度问题扩展为更一般的情况，有助于提高吊机利用率，降低运作和物流成本、增强企业竞争力。

本项目从钢铁企业实际生产过程和存取过程两大方面提炼的吊机调度问题进行了研究，一是针对钢卷仓库为背景，对倒垛与运输集成的吊机调度问题进行研究。另一方面，针对钢铁企业实际的罩式退火过程，对装载与卸载集成的吊机调度问题进行研究。根据不同问题的实际特征，分别分析了吊机调度解的结构特征和最优解性质；建立了吊机集成调度的线性规划模型，并进一步证明了问题的复杂性。对于已证明为NP难问题的单吊机调度，构造了求解问题的启发式算法从而确定吊机对物件搬运过程中装载、卸载、倒垛、堆垛等各类操作的吊机路线及移动时间表；对于多吊机同时调度的各类情况，为避免碰撞保证问题的可行，讨论了多吊机同时操作的各种可能情况，根据对问题最优性质的分析，进一步构建启发式算法及符合问题特征的智能优化算法，并分别从算法的理论性能和数值计算实验角度给出了分析。实验结果表明，所构造的求解吊机集成调度的近似算法，在合理的可接受的时间内可以求出问题的近优解。因此，本项目的研究为钢铁企业物件空间搬运与时间集成吊机调度提供了基础理论与方法支持，是吊机调度理论向实际应用发展的一次有益探索。