Abstract: In real production process of precast components manufacturing,an order often contains multiple jobs.To meet customer delivery time and facilitate management,it is necessary to processing jobs from the same order continuously.Thus,it is crucial to solve the Joint Optimization Problem of Inter Order Scheduling and Intra Order Scheduling (JOP_IOSIOS).JOP_IOSIOS is more complicated than the traditional flowshop scheduling problem,is also a NP-hard problem.To solve this problem,based on the Just-in-Time (JIT) policy,a mixed-integer programming model was formulated to minimize the total earliness and tardiness penalties through analyzing the process constraints,inter-order constraints and intra-order constraints in-depth.In view of the complexity of the problem,an effective Co-Evolutionary Hybrid Genetic Algorithm—Discrete Differential Evolution algorithm (CoHGA-DDE) was proposed based on the ideas of decomposition and co-evolution.The main idea was to construct two populations at first,then adopt different evolutionary strategies to optimize them,and finally improve the performance through the interaction of two populations.To verify the effectiveness of the co-evolutionary framework and the proposed method,a Co-Evolutionary Genetic Algorithm (CoGA),a Co-Evolutionary Discrete Differential Evolution (CoDDE),a Genetic Algorithm (GA),a Discrete Differential Evolution (DDE) and an Iterative Greedy (IG) algorithm were designed.Through testing on orders of different sizes,the calculation results showed that CoHGA-DDE achieved the best solution quality and strongest robustness under the co-evolution framework.Compared with the heuristic which was often adopted by a precast manufacturer,the proposed algorithm improved solution quality obviously,which was expected to reduce production cost,improve on-time delivery rate and ensure construction progress.

Key words: precast scheduling, joint optimization, co-evolution, genetic algorithms, differential evolution

摘要： 在预制构件实际生产过程中,通常一个订单中包含多个工件。为满足客户交货期和方便管理,来自同一订单的工件需要连续生产,就需要解决订单间调度与订单内调度的联合优化问题(JOP_IOSIOS)。该问题是比传统流水线调度问题更为复杂的问题,是典型的NP-hard问题。为解决该问题,通过对工序约束、订单间、订单内约束等的深入分析,基于准时制生产模式,以最小化总提前和拖期惩罚费用为目标建立了混合整数规划模型。鉴于问题的复杂性,基于分解与协同进化框架,提出一种有效的协同进化混合遗传—离散差分进化算法(CoHGA-DDE)。其主要思想是首先构造订单间调度种群和订单内调度种群,然后对两个种群分别采用离散差分进化策略和遗传进化策略,并通过两个种群之间的交互作用来提高各自性能。为验证协同进化框架和CoHGA-DDE的有效性,设计了协同进化遗传算法(CoGA)、协同进化离散差分进化算法(CoDDE)、遗传算法(GA)、离散差分进化算法(DDE)、和迭代贪婪(IG)算法。对不同规模订单进行测试,计算结果显示,与GA,DDE和IG相比,协同进化方法具有更好的求解质量和鲁棒性,而在协同进化方法中,CoHGA-DDE具有最好的求解质量和鲁棒性。与实际预制生产过程中常用的启发式方法相比,CoHGA-DDE具有显著的平均改进率,有望降低生产成本、提高准时交付率和保证施工进度。

关键词: 预制构件生产调度, 联合优化, 协同进化, 遗传算法, 差分进化