Research On Iterated Greedy Algorithm For Distributed Blocking Flowshop Scheduling Problem

The scheduling optimization of the job-shops is a basis approach for manufacturing enterprises to realize the rationalization,automation and intellectualization of the production process,and improve productivity as well as enterprise competitiveness.Blocking flow shop scheduling problem is one of the classical job-shops scheduling problems,which widely exists in chemical manufacturing,steel manufacturing and electronic device manufacturing.With the development of distributed manufacturing mode in recent years,distributed flowshop scheduling problems have become a hot topic in the field of shop scheduling.This thesis studies the distributed blocking flowshop scheduling problem(DBFSP).The iterated greedy(IG)algorithm is applied to minimize makespan,total flowtime,as well as makespan and total energy consumption,respectively.The main work is as follows.(1)An enhanced IG algorithm is proposed to solve DBFSP with minimizing makespan criterion.First,an effective heuristic is proposed to generate a good initial solution.Second,the destruction and reconstruction are improved for a more effective exploration,in which the characteristic of critical factories is utilized to destruct and the reinsert strategy enhances the reconstruction procedure.Third,three local searches that explore different neighborhoods are proposed to improve the local exploitation capability.Fourth,a new temperature calculation method of the simulated annealinglike acceptance criterion is adopted to jump out of local optimality more effectively.Finally,simulation results show the superiority of the proposed IG algorithm.(2)A population-based IG is presented to minimize the total flowtime for DBFSP.The proposed algorithm integrates the population mechanism into IG to improve global exploration capability.The proposed DWPFE heuristic can generate the initial population with both good quality and diversity despite little computational effort.Three different procedures to generate the offspring solutions are developed,each of which rationally combines the destruction,reconstruction,and selection operator.The acceleration evaluation procedure of the insertion and swap neighboring solutions are proposed,then three local searches are proposed.Simulation results reveal the effectiveness of the proposed algorithms.(3)A knowledge-based multi-objective IG algorithm is proposed to simultaneously optimize the maximum completion time and total energy consumption,considering the factory heterogeneity as well as the green scheduling in DBFSP.First,the proposed algorithm consists of two stages.In the first stage,iterative greedy search is carried out for the processing sequence under different machine speed matrices,and in the second stage,global iterative greedy search is carried out for the processing sequence and the processing speed based on the search results of the previous stage.Second,according to the characteristics of the problem,the destruction reconstruction methods are designed for the two stages respectively.Then,an energy-saving procedure and a local search method are proposed to enhance the local exploitation capability of the second stage.Finally,simulation results verify the effectiveness of the proposed algorithm.