不确定条件下基于遗传算法的作业车间调度问题

Job shop scheduling with uncertainty based on genetic algorithm

考虑到产品不同的交货期,研究了不确定条件下的作业车间调度问题,用三角模糊数表示产品处理时间,建立了调度问题的模型,并结合模糊理论设计了一种改进的遗传算法进行求解.该算法通过整数编码的方法产生初始种群,结合轮盘赌方法和精英保留策略进行选择操作,采用基于优先工序交叉(precedence operation crossover,POX)算子和互换变异方法进行交叉和变异操作,并通过动态调整交叉概率和变异概率的方法来提高算法的性能以及计算效率.最后,通过算例和企业实例验证了该模型和算法的有效性.

A mathematical model representing uncertain processing time by triangular fuzzy number was built to deal with the job shop scheduling problem with different due date windows. An improved genetic algorithm was developed to solve the problem. The algorithm generated initial population using an integer coding method combined with a roulette method and the elitist strategy in the selection operator. Precedence operation crossover （POX） and swap mutation methods were used in crossover and mutation operators. Meanwhile, crossover and mutation probabilities were dynamically adjusted to im- prove the algorithm＇s performance. An example was given to verify validity of the model and algorithm.