Abstract: To deal with the problems of tight order due date and limited production capacity in the precast production system, an integrated optimization model for order acceptance and scheduling is established to maximize the total net revenue based on fully considering the characteristics of complex production processes, such as interruptible and uninterruptible processes, serial and parallel situations. In view of the NP hardness of the problem and the high nonlinearity of the model, a hybrid iterated greedy (HIG) framework is proposed by integrating the properties of the schedules, constructive heuristic, local search and mechanism of destruction-construction. Aiming to improve the solution quality and search efficiency of the algorithm, in the construction steps of the proposed algorithms, two speedup strategies are designed by using order insertion properties. Computational results show that the proposed algorithms perform better than hybrid genetic algorithm and tabu search (GA_TS), genetic algorithm (GA) and tabu search(TS). It also demonstrates that the speedup strategies can effectively shorten the running time of the algorithms, which could improve the total net revenue and customers' satisfaction of prefabrication enterprises.

Key words: precast permutation flow shop, order acceptance and scheduling, hybrid iterated greedy algorithm, speedup construction strategies

摘要： 针对预制构件生产管理过程中订单工期紧和生产能力不足的问题,在充分考虑中断和不可中断工序,串行和并行工序等复杂工况特点的基础上,以最大化净利润为目标,建立了一种订单接受与调度集成优化模型。鉴于问题的NP难性和模型的高度非线性,通过集成问题性质、构造启发式、邻域搜索和破坏-构造机制,提出了一种混合加速迭代贪婪搜索框架。其中,在调度构造阶段,为提高算法求解质量和搜索效率,设计了两种融合订单插入操作性质的加速构造策略。计算结果显示,与混合遗传禁忌搜索算法,遗传算法以及禁忌搜索算法相比,本文所提算法具有更好的求解质量和搜索效率。同时验证了所提出的加速构造策略能够有效减少算法运行时间。该研究有望显著提高预制生产企业净利润和客户满意度。

关键词: 预制构件流水车间, 订单接受与调度, 混合迭代贪婪算法, 加速构造策略