Abstract: Multiprocessor task scheduling widely arises in manufacturing industries.To solve multiprocessor task scheduling optimization in realistic flexible flow-shop environments,a Multiprocessor Task Scheduling Problem in multi-stage Flexible Flow-Shops (MTSP-FFS) was studied with transportation time and job release time.This problem was NP-hard.An integer programming model of MTSP-FFS was then formulated with the objective of minimizing maximal completion time.For solving this problem,firstly,the generation procedure of machine flow for job processing and the matrix coding scheme of machine flow for single job processing and lot job processing were proposed.Then,Job Allocation Procedure with Randomly Selecting from Idle Machines (JAP-RSIM) was designed so that the original solutions of JAP-RSIM were obtained.New solutions were filtered based on the minimization of maximal completion time.Further,the new solution updating process of crossover and mutation was presented based on the synchronization of workpiece sequence and processing machine flow,and the Iterative Greedy Procedure (IGP) was applied to complete the adjustment and reconstruction operations.The new scheme was generated to improve the solution quality.Finally,the GA&IGP optimization strategy was formed.Simulation experiments compared the three algorithms of GA,IGP and GA&IGP for the different sized problems which were measured by the deviation percentage of the lower bounds.Testing results showed that the GA&IGP optimization algorithm could obtain better near-optimal solutions.

Key words: multiprocessor task scheduling, flexible flow-shops, machine flow for job processing, iterative greedy procedure, genetic algorithm

摘要： 多处理器任务调度在制造业有着较广泛的应用,为了解决实际柔性流水车间环境下的多处理器任务调度优化问题,研究了考虑运输时间和释放时间的多阶段柔性流水车间多处理器任务调度问题,该问题为NP-hard问题,以最小化最大完工时间为目标建立了柔性流水车间多处理器任务调度整数规划模型。为有效求解该问题,首先研究了工件加工机器流生成机制、单工件加工机器流矩阵编码方案和批量工件加工机器流编码方案。进而设计了基于机器空闲随机筛选的工件安排机制,产生该规划的初始解生成方法,以最小化最大完工时间原则进行新解筛选。然后构建基于工件顺序与加工机器流同步交叉的新解更新过程、基于工件顺序与加工机器流同步变异的新解调整过程,并利用迭代贪婪算法完成调整和重建操作,产生全新方案以改善求解质量,最终形成结合迭代贪婪算法的混合遗传融合优化策略。仿真实验利用解的下界得出偏差百分比,分别用遗传算法、迭代贪婪算法和混合遗传融合优化算法对不同规模的问题进行测试,结果表明,混合遗传融合优化算法能够获得较好的近优解。

关键词: 多处理器任务调度, 柔性流水车间, 工件加工机器流, 迭代贪婪过程, 遗传算法