具有多处理机任务约束的混合作业车间调度建模与嵌入式仿真

With the multi-species and small batch becoming the main production mode of discrete manufacturing companies, job shop with multiprocessor tasks for efficient scheduling is an urgent problem of these enterprises to be solved and is gradually becoming the hot study issue of researchers. The project will study the Hybird Job-shop Scheduling with Multiprocessor Task (HJSMT) problem. .Firstly, a heuristic algorithm based on Particle Swarm Optimization (PSO) is developed to solve the deterministic HJSMT problem. Since there are many uncertainties in the actual production, the processing time of jobs cannot be accurately predicted. Assuming the jobs with random processing time, the embedded simulation technology is used to simulate the stochastic HJSMT problem and the heuristic algorithm based on PSO is proposed for task allocation. The simulation results can provide an important and meaningful reference for the actual production scheduling..The anti - risk is most often considered by scheduling policy makers, so we use the Scenario method to describe the random processing time and establish expectations - variance model and robust optimization model of stochastic HJSMT. The solution of the robust optimization model not only has good expectations, but also has a certain ability to resist risks, and it can provide the optimal scheduling risk decisions to the risk avoidance decision-makers.

随着多品种、小批量逐渐成为离散制造企业的主要生产模式，如何对具有多处理机任务的作业车间进行高效排产已成为许多离散制造企业亟待解决的问题，同时也逐渐成为国内外学者研究的热点。本项目针对具有多处理机任务约束的混合作业车间调度（HJSMT）问题进行研究。首先针对确定性HJSMT问题，设计出基于粒子群算法的启发式求解算法。由于在实际生产中会具有许多不确定性，使得工件加工时间无法精确预知，因此本项目假设工件具有随机加工时间，采用嵌入式仿真技术对随机HJSMT问题进行仿真求解时，利用基于粒子群的启发式算法进行任务分配，得到的调度仿真结果可为实际调度提供重要和有意义的参考。抗风险是调度决策者最常考虑的因素，本项目采用Scenario方法来描述随机加工时间，建立期望-方差模型和鲁棒优化模型并进行求解，使得到的调度决策不仅具有较好的期望值，而且还具有一定的抗风险能力，为风险规避型决策者提供最优调度风险决策。

车间调度在制造企业的生产管理中占有重要位置，具有提高企业生产效率、降低成本以及增强市场竞争力等重要作用。在离散制造企业车间中，经常会遇到某些任务需要多台处理机（指设备或者工人等）同时加工/处理的情形，这种具有多处理机任务加工需求的作业车间调度问题被称为“具有多处理机任务约束的混合作业车间调度”（Hybrid Job-shop Scheduling with Multiprocessor Tasks， HJSMT）。这类调度问题在实际生产中非常普遍，因此开展对HJSMT的研究具有重要的理论意义和应用价值。. 本项目首先对HJSMT问题进行分析，建立数学模型，并设计出性能优良的求解算法。具体地，从HJSMT的一个简化模型入手，首先研究单工序HJSMT问题，然后在此基础上扩展至一般的多工序HJSMT问题。此外，还分别研究了处理机无差异和处理机有差异的HJSMT问题。不仅构建了不同类型的HJSMT调度数学模型，设计出混合粒子群优化算法以求解问题，而且还设计出改进型分散算法进行求解，并得到满意的寻优结果。对粒子群算法的改进工作包括：设计粒子的编码策略、确定粒子信息交换的方式、确定适应值函数、增强算法的局部搜索能力等。对分散算法的改进工作包括：设计出能够产生主动调度的编码和解码方案、新的初始解产生方法、产生新解的合并操作以及基于本地搜索与禁忌搜索的双层优化方法等。. 在仿真研究方面，本项目针对JSP调度和HJSMT调度建立数学模型，根据数学模型和生产流程抽象出仿真模型。同时，考虑到遗传算法局部搜索能力较弱，因此结合优先调度规则设计出混合遗传算法对仿真模型进行优化。通过仿真软件Plant Simulation实现了嵌入式仿真模型，并通过实验证明所提出的模型和优化算法是可行、有效的。. 在风险决策研究方面，本项目建立了混合多处理机任务作业车间调度（HJSMT）的鲁棒优化模型。在建模过程中将可预测的不确定因素抽象为工序加工时长的变化，并采用场景分析法加以描述。在分析传统鲁棒优化模型优劣的基础上，提出新的期望-最坏场景鲁棒优化模型（ECWM）。通过仿真实验验证了ECWM的有效性，且结果表明由ECWM得到的调度在具备良好平均性能的同时也具有较好的抗风险能力。