基于遗传禁忌算法考虑转运约束的并行机批量调度问题研究

Research on Parallel Machine Batch Scheduling with Transport Constraints Based on Improved Genetic Tabu Algorithm

在多品种混流生产车间里,广泛存在着各种批量的任务在多台并行机上调度优化问题。这种并行机批量调度需要考虑批量大小设置、加工顺序优化、设备充分利用等多种要素,是一类典型NP-hard问题,且当任务加工完后还需要考虑转运过程时,问题将变得更加复杂。为了减少并行机生产过程中任务拖期和在制品积压,寻求更好的生产调度方案,针对典型并行机生产和转运场景,以最小化加权完工时间及拖期工件的惩罚费用、作业切换成本、库存成本之和为优化目标,设计了基于启发式规则的仿真程序与遗传禁忌算法相结合的优化算法,研究单工序不相关并行机调度环境下车间批量调度的最优调度方案,再通过案例验证了本文优化算法的有效性。结果表明,优化算法得出的并行机批量调度方案使得作业切换次数和拖期订单大大减少,减少在制品库存的同时提高了转运资源的利用率。

The scheduling optimization problem with various batch tasks on multiple parallel machines widely exists in multi-variety mixed-flow production shop. This kind of problem needs to consider batch size,processing sequence optimization,full utilization of the equipment and other elements. It is a typical NP hard problem. When the task after processing also needs to be considered during the transfer process,the problem will get more complicated. In order to reduce task delay and work-in-process backlog in parallel machine production,to get a better production scheduling result,an optimization algorithm based on heuristic rules and genetic tabu algorithm was designed in order to minimize the sum of weighted completion time,penalty cost,job switching cost and inventory cost.This paper studied the optimal scheduling method of batch shop scheduling under single process uncorrelated parallel machine scheduling environment, and verified the effectiveness of the optimization algorithm through a case study. The results show that the parallel machine batch scheduling method obtained by the optimization algorithm,can greatly reduce the number of job switching and delayed orders,reduce the work-in-process inventory and improve the utilization rate of transfer resources.