基于遗传算法的Job Shop调度问题研究

在多平行工作站环境下,为使限定资源分配下的车间调度问题(Job Shop problem,JSP)具有最小总延迟时间;同时又可设定各订单具有不同的开工日(release date)及到期日,提出以可开工时间与结束时间为基础的分解解法,并在遗传算法的基础上构造混合遗传算法(hybrid genetic algorithm,HGA)来实现目标设定。实验结果表明,HGA在问题求解质量与Lingo解的最佳解差异在15%以内,并具备较基本型遗传算法更佳的稳定性。结果显示该算法可帮助管理人员实现智能资源配置与订单调度。

Based on genetic algorithm for Job Shop scheduling problem

This study addressed a job scheduling and resource allocation problem with distinct release dates and due dates to minimize total tardiness in parallel work centers with a multi-processor environment. To solve the problem, this study also proposed a hybrid genetic algorithm (HGA) with release and due dates based decomposition heuristic. Experimental results show that the percentage deviations between the HGA and Lingo are smaller than 15%, and the HGA has smaller variance than the GA. This study proposed a decision-supporting model, which integrated simulation, genetic algorithms and decision support tools, for solving the JSRA problem by practical perspective.