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

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