Research On Flexible Job-shop Scheduling Problem Based On Differential Evolution Algorithm

Flexible job shop scheduling problem widely exists in practical production system.Proper and effective scheduling can help cut lead times, improve on-time delivery. Thescheduling problems in real world are complex, dynamic and require different sets ofevaluation criteria. All these criteria often conflict with each other and the schedulestrategy should response to the dynamic events instantly.Firstly, in this paper, a modified differential evolution algorithm is presented for theflexible job-shop scheduling problem with makespan criterion. A new machineassignment strategy is proposed to improve the initial population, and a populationimprovement strategy is performed when the best solution of the population does notimprove during some generations. This proposed algorithm is tested on a series ofbenchmarks instances. Experimental results show that this algorithm is efficient andcompetitive compared to some existing methods.Secondly, a research on the effect of different reschedule periods is developed.Probabilistic method is applied to assign the arrival time for each job and a periodicrescheduling strategy is performed by locating these jobs into corresponding scheduleintervals. In every schedule interval, the multi-objective flexible workshop dynamicscheduling was established according to the objective criteria of efficiency and stability. Amodified mutation operation and a multi-stage selection operation for multi-objectiveoptimization are proposed in this paper. A Pareto solution based multi-objectivedifferential evolution algorithm is performed to solve the scheduling problem in everyschedule interval and a final schedule was selected from the non-dominated solutions.Experimental results show that the proposed algorithm is more effective than othermulti-objective algorithm. The methodology is tested on a simulated job shop of500jobsarrive randomly on different rescheduling periods to determine the impact of the keyparameters on the performance measures.At last, a research on the dynamic schedule of the flexible job shop problem based onperiodic and event-driven strategy is developed. The rolling horizon rescheduling strategyis performed by convert the dynamic schedule into some successive schedule intervals. Inevery schedule interval, a Pareto solution based multi-objective differential algorithm isapplied with the criteria of makespan, total tardiness and total deviation cost. A simulationtest is performed to verify the feasibility of the scheduling strategy and optimization of thealgorithm considering the dynamic events of emergency order, machine failure/available,general order.