运输与倒垛集成的多吊机调度问题

Coordinate Transportation and Shuffling Operations in Multi-Crane Scheduling Problem

考虑了钢铁企业仓库管理中经常出现的多吊机调度问题.根据实际存储的需求,每个板卷已经被放在了预先指定的按两层摆放的位置上.当给定一些需求板卷时,如果一个需求板卷在上层或无板卷阻碍的下层,它可以被直接运输到指定位置(运输操作);否则,阻碍板卷需要首先被运到另外的位置(倒垛操作).所研究的问题为由吊机协调调度运输和倒垛操作.在以前研究的文献中,这两种操作都是分开研究的.目标为最小化最后一个运输到指定位置的板卷完成时间,这与最后结束操作的吊机的最早可能完工时间一致.为了更清楚地描述问题,提出了一个混合整线性规划模型(MILP).由于证明了所研究问题的特殊情况是强NP难的,这意味着所研究的问题也是强NP难的,因此提出了问题的启发式算法,给出了下界并进一步分析了算法的最坏性能.

A multi-crane scheduling problem commonly encountered in real warehouse operations in steel enterprises is considered. As the practical storage technological requirement, each coil has been stored on its pre-specified position of two levels. Given some demanded coils, if a demanded coil is in upper level or in lower level without being blocked by coils, it can be picked up directly to designated place~ else, the blocking coils need to be picked up to another position first. Unlike previous literatures in which both operations have been considered to be scheduled separately, the problem schedules transportation operation and shuffling operation coordinately. The objective is to minimize the last demanded coil transported to its designated place which is consistent with the earliest possible completion time of one crane. For describe the studied problem clearly, it is first formulated as a mixed integer linear programming （MILP） model. Since the special case of the problem under study is strongly NP hard, it implies that the problem is also strongly NP hard. Hence, a heuristic algorithm is proposed. A lower bound to the problem is developed and further the performance of the algorithm is further analyzed from the worst case point of view.