共享柔性资源约束下的多机并行作业排程调度问题研究
Unrelated Parallel Machines Scheduling with Shared Flexible Resources

随着C2B定制化生产模式的兴起，催生了多品种小批量的生产方式。这种方式会导致各类生产任务在机器上频繁切换，容易造成产能浪费和机器损耗。同时，在多机并行生产的过程中，经常需要共享一些柔性资源，如人力、库存缓冲区、特定生产设备等，因此需要精巧的生产排程计划来合理协调多种共享资源的利用，减少产能浪费。本文以并行机器调度问题为研究对象，研究了以最小化最大完工时间以及切换时间为目标的多机并行调度问题。在满足经典并行机调度问题的约束条件下，同时考虑了多种共享柔性资源约束。针对该NP-hard问题，本文设计了基于禁忌搜索的超启发式算法进行求解优化，采用禁忌搜索算法作为高层次启发式策略，并结合并行机作业的调度特点设计了7种LLH来构成低层次启发式算法池，通过算例分析验证了算法的有效性。最后通过不同规模的数值分析对多种共享柔性资源的影响进行分析，结果表明人力资源和共享产线容量的增加都会改善排程的目标，然而这两种资源的边际效应是随之递减的。由于资源的使用以及扩容都需要一定成本，因此科学选择合适的人力资源水平以及共享产线的容量对提高整体效率非常重要。
With the rise of C2B customized production mode, multi-variety and small-batch production mode has been spawned. This way will lead to frequent switching of various production tasks on the machine, which is easy to cause capacity waste and machine loss. At the same time, in the process of multi-machine parallel production, it is often necessary to share some flexible resources, such as manpower, inventory buffer, specific production equipment, etc. Therefore, exquisite production scheduling is needed to rationally coordinate the utilization of various shared resources and reduce capacity waste. In this paper, the unrelated parallel machine scheduling problem is studied to minimize the maximum completion time and switch time. Under the constraints of the classical parallel machine scheduling problem, multiple shared flexible resource constraints are considered at the same time. To solve the NP-hard problem, this paper designs a hyper-heuristic algorithm based on tabu search for optimization. Tabu search algorithm is used as a high-level heuristic strategy. Combined with the scheduling characteristics of parallel machine jobs, seven low-level heuristics are designed to form a low-level heuristic algorithm pool. The effectiveness of the algorithm is verified by an example. Finally, the impact of multiple kinds of shared flexible resources is analyzed by numerical analysis of different scales. The results show that the increase of worker resources and shared production line capacity will improve the scheduling goals, but the marginal effect of these two kinds of resources decreases accordingly. Due to the cost of resource utilization and expansion, it is important to scientifically choose the right level of worker resources and share the capacity of production line to improve the overall efficiency.