缩短最大完工时间的船舶分段空间调度算法

A Spatiotemporal Scheduling Algorithm Minimizing Makespan

针对船舶分段的空间调度,考虑船舶建造过程中的时间和空间两大资源要素,构建了时空利用率模型并以此为评价目标.运用形状相似和工艺相似策略,提出了一种缩短最大完工时间的船舶分段空间调度算法.给出了评价时间和空间等资源利用效率的指标,并利用图论的方法提供了具体空间调度的直观结果.结合船舶建造厂的实际数据进行了数据分析和实例验证,无论空间调度的质量还是效率都取得了令人满意的结果.

To solve some problems arising in block assemble shop, a spatial scheduling algorithm was proposed aiming at shortening makespan by using the maneuvers of shape resemblance and craft resemblance. In the algorithm, the most essential resources in shipyard such as time and spatial layout are investigated, and the model of spatiotemporal utilization ratio is expatiated and established as the benchmark in optimizing and evaluating the algorithm. Then, several targets for evaluating the time and space utilization ratio were studied and an intuitionistic scheduling result by graphic mode was also proposed. Finally, the algorithm was validated using abundant experimental work pieces and applied to solve a real spatial scheduling. The result shows that satisfactory spatial scheduling performance and efficiency can be achieved in a short time.