带组合缓冲约束的柔性流水车间调度优化

Optimization on Flexible Flow Shop Scheduling with Mixed Buffer Constraints

研究了每道工序包含多台不相关并行机的柔性流水车间调度问题,部分工序间具有无等待约束,考虑工序间运输时间和工件动态到达的实际生产特征,以最小化总加权完成时间为目标,构建了整数规划模型,提出了一种融合迭代贪婪算法和遗传算法的改进贪婪遗传算法。首先,利用二维矩阵编码表述调度解,结合CDS(Campbell-Dudek-Simth)启发式算法和随机程序共同产生初始解;其次,设计基于工序位的交叉和基于工件位的变异操作得到改进的遗传算法解;最后,由于上一代中适应度较低的较差个体会直接影响下一代的遗传操作,为避免早熟,引入结合局域搜索的迭代贪婪算法,从遗传算法产生的种群中筛选出较差个体,对其执行破坏和重建操作,并设计基于工件位的成对交换、成对插入和重新排序的3种邻域生成机制以进行局域搜索。通过仿真实验测试所提算法与几种启发式算法,对比结果表明,所提出的改进贪婪遗传算法能获得更好的近优解。

The flexible flow shop scheduling is studied where there are multiple unrelated parallel machines at each operation and some operations are no-wait constrained.Considering the actual production features of transportation time and job dynamic arrival,an integer programming model is formulated with the objective of minimizing the total weighted completion time.An improved greedy genetic algorithm combining iterated greedy algorithm with genetic algorithm is then proposed.Firstly,two-dimensional matrix encoding is applied to describe the scheduling solutions.CDS heuristic and a random procedure are used to generate the initial solutions.Secondly,an operation position based crossover operation and a job position based mutation operation are designed to obtain the improved solutions of genetic algorithm.Finally,an iterated greedy algorithm with local search is introduced including the following process.Destruction and reconstruction operations are performed on the poor individuals selected from the population generated by genetic algorithm.And three neighborhood formation schemes of pairwise exchange,pairwise insertion and reordering based on job position are developed to perform local search.Simulation experiments are made on the proposed algorithm and several heuristic algorithms and the results show that the proposed improved greedy genetic algorithm can obtain better near optimal solutions.