传搁时间约束下的运输与批处理机生产协调调度

针对炼钢模铸系统钢锭高温运作的特点,提出带有传搁时间约束的生产前运输与批处理机生产协调的调度问题.工件的加工时间依赖于其传搁时间,每批工件的加工时间为该批工件中加工时间最大值.目标函数为最小化总完工时间与生产费用的线性组合.通过复杂性分析,证明该问题是强NP难解问题.建立混合整数规划模型,基于动态规划提出两种特殊情况的最优算法,设计原问题的启发式算法并进行最坏情况下性能比分析.实验仿真结果验证了所提出启发式算法的有效性与稳定性.

Coordinated scheduling of transportation and production on batching-machine with tracking time constraint

For the feature of the steelmaking-molding with high temperature operations in the iron and steel industry, a coordinated scheduling problem with transportation before production on a single batching machine under the tracking time constraint is addressed in this paper. The processing time of a job is dependent on its tracking time. The processing time of a batch is the largest processing time among the jobs assigned to this batch. The objective is to minimize the total completion time and the total production cost. A mixed integer programming(MIP) model with production and transportation is developed. It is proved that the problem is strongly NP-hard through complexity analysis. Based on dynamic programming, optimal algorithms for two special cases are derived, and a heuristic algorithm is presented with its worst-case performance analysis. The simulation results show the effectiveness and stability of the heuristic algorithm.