A modified differential evolution for uniform parallel machines scheduling problem with minimizing makespan

作者：Niu Qun^*; Zeng Ting Ting; Zhou Zhuo

来源：Journal of Dong Hua University (english Edition), 2012, 29(3): 272-279.

• Comparison result
• Control parameters
• Differential Evolution
• High quality
• Largest processing time
• Makespan
• Minimizing makespan
• Modified differential evolution
• Mutation operations
• Optimal solutions
• Optimization method
• Polynomial-time
• Roulette wheel selection
• Scheduling jobs
• Uniform machine
• Uniform parallel machine scheduling
• Uniform parallel machines

The problem of scheduling jobs on uniform parallel machines with makespan (Cmax) minimization objective was studied. Due to its non-deterministic polynomial-time (N) hard nature, it is difficult to achieve an optimal solution with traditional optimization methods. For this reason, a novel modified differential evolution (MDE) was proposed to tackle the uniform parallel machine scheduling problem (UPMSP), taking out the mutation operation and introducing the roulette wheel selection strategy into conventional differential evolution (DE). In MDE, more high quality individuals can be reserved to update the population. And the control parameter F in conventional DE was removed, which could simplify the DE. To verify the proposed MDE, 162 randomly generated instances were conducted. The comparison results with DE, genetic algorithm (GA), simulated annealing (SA), and largest processing time (LPT) method show that the MDE is an efficient and competitive approach in solving UPMSP.

• 出版日期2012
• 单位上海大学