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

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

项目编号： No.71201104

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 管理科学与工程

项目作者： 谢谢

作者单位： 沈阳大学

项目金额： 19万元

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

中文关键词： 吊机；集成调度；复杂性分析；近似算法；性能理论分析

英文摘要： 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, a

英文关键词： Crane；Integrated scheduling；Complexity analysis；Approximation algorithm；Performance theoretical analysis