考虑投放期、交货期和机器准备时间的平行机问题改进遗传算法

针对考虑工件投放期、交货期和机器准备时间的平行机问题，分别以最小化最大机器完工时间和最小化工件总延期惩罚费用为优化目标，建立相应的平行机问题模型，提出一种求解该问题的改进遗传算法。该算法中采用了基于工件和机器的多参数级联编码，染色体由工件子串和机器子串连接而成；提出了机器的加工能力、加工能力指数和冗余机器集的概念及相应的初始种群生成方法；对工件子串采用部分映射交叉，而对机器子串不作交叉运算；在变异算子中，提出基于机器负荷的启发式变异算子。

Improved Genetic Algorithm for Parallel Machine Scheduling with Release Dates, Due Dates and Machine Ready Time Considered

This paper first models a kind of parallel machine scheduling with release dates,due dates and machine ready time considered.The model has minimized makespan and minimized total job delay penalty as the objectives.Then an improved genetic algorithm is proposed,where job and machine-based multi-parameter cascade encoding is adopted and a chromosome is obtained by connecting job substring and machine substring.Machine process capability,machine process capability index and redundant machine set are defined,and initial population producing method is given.Job substrings receive partially mapped crossover,but machine substrings do not go through any crossover.With regard to mutation operator,a load-based heuristics(LBH) mutation is presented.The experimental results indicate that the improved genetic algorithm works well with regard to the parallel machine scheduling proposed in the paper.