预制构件流水车间订单接受与调度的集成优化

熊福力, 储梦伶

(西安建筑科技大学 信息与控制工程学院,陕西 西安 710055)

0 引言

装配式建筑在城市可持续发展方面具有非常明显的优势，预制构件生产是装配式建筑行业发展的关键，对于提高装配式建筑生产效率和降低能耗，具有重要的现实意义。但预制构件的生产处理过程相比于传统流水车间调度问题更加复杂。迄今为止，预制构件生产调度方面已有较多研究[1～3]，但均是假定订单固定的情况下对工件生产做出调度决策，而未考虑预制构件生产能力限制和客户交货期要求。在日益激烈的预制构件生产竞争环境下，为避免过高的惩罚费用并追求利润最大化，预制构件制造商通常在计划周期前并不盲目接受所有订单，而是需要根据预制构件企业实际生产能力和订单交货期等实际情况，对订单做出选择，选择那些可以获得更多利润的订单，进而安排订单生产调度。因此该问题比传统预制生产调度问题更为复杂，需要对订单选择和生产调度做出综合决策，从而增加预制构件制造企业总利润和客户满意度，我们将此问题称为预制构件订单接受与调度问题(Order acceptance and scheduling under precast production environments, OAS_PPE)。

对于订单接受与调度问题，Rom和Slotnick[4]研究了单机环境下带拖期惩罚的订单接受与调度问题。Chen，Lu和Yang[5]提出混合进化算法下生产调度的并行优化，其目标函数是最小化顺序相关的过渡成本和非执行处罚。Nobibon和Leus[6]求解了单机环境下订单接受与调度问题的精确算法。王柏琳等[7]研究了置换流水车间对工件拒绝和工件调度的联合决策。以上研究均是基于单机调度或者传统置换流水车间调度环境。虽然订单接受与调度问题在实际预制构件生产管理过程中时有发生，但这方面的相关研究尚未见报导。

本文针对OAS_PPE问题，以净利润最大化为目标，根据预制构件企业实际生产能力和客户交货期要求，同时对订单选择和生产调度进行决策。与已有的OAS研究不同的是[8～11]，预制构件生产过程由于存在可中断和不可中断，串行和并行工序并存等复杂工况特点，使得OAS_PPE问题是比传统流水车间调度问题更为复杂的多决策离散集成优化问题，同时由于工艺约束中带有高度非线性，因此难以利用传统的流水车间调度模型及方法进行有效求解。

近年来，遗传算法(Genetic algorithm, GA)、禁忌搜索(Tabu search, TS)、混合遗传-禁忌搜索(Hybrid GA and TS，GA_TS) 和迭代贪婪(Iterated greedy algorithms, IG)等智能优化算法在求解流水车间调度问题上取得了很多成功应用[12～14]。其中IG算法占有较为明显的优势[13,14]。Ruzi等[13]设计了分布式置换流水车间调度问题的迭代贪婪方法。Ribas等[14]针对有阻塞流水车间调度问题提出了一种迭代贪婪算法，在计算时间和求解质量上取得了较好的效果。鉴于此，本文将通过深入挖掘特定问题性质，集成构造启发式、邻域搜索结构以及破坏-构造机制，提出有效的混合迭代贪婪搜索框架，克服整数变量、多决策属性和大量非线性复杂约束带来的求解困难，有效提升求解质量和搜索效率，并有望显著改善预制构件制造企业的净利润。

1 OAS_PPE问题描述与模型建立

1.1 问题描述

预制构件生产流程要依次经过模具组装、预埋件安装、浇筑、养护、拆模以及精加工六道工序，具有流水生产特点，但与传统流水线不同的是，预制构件生产流水线具有串并行混合生产的特点，在蒸汽养护阶段，多个蒸汽养护室可以同时对多个工件进行并行处理，而其他五个生产阶段则属于串行生产阶段，同一时刻只能处理一个订单任务。同时从预制构件生产实际出发，考虑了每天12个小时的非工作时间，这个时间段内需要工人参与的生产过程将无法进行，而传统的流水生产过程通常假设一天24小时均可以利用；预制构件各个生产过程具有可中断和不可中断混合生产的特点，在浇筑阶段，一旦开工，则不允许中断；在模具组装、预埋件安装、拆模以及精加工等生产阶段，如果在加班之后还无法完成，则允许中断，未完成的工作将推迟到下一个工作日完成，而传统的流水生产过程则假设各个阶段的生产过程是不可间断的。

基于以上预制构件生产背景，本文所研究的OAS_PPE问题可描述如下：预制构件制造企业共收到J个订单，记为J= {1,2,…,J}。在该计划周期结束前不插入其他生产计划。通常由于交货期要求和生产能力限制，为减少由于订单拖期导致的高额惩罚费用，预制构件制造商必须选择性接受订单以获取更多利润。其中Tj:max{0,Cj,6-d}表示订单j的拖期时间。如果接受订单j，则订单j的净利润为Qj-wjTj。企业需要同时确定接受的订单集合与生产排序，从而最大化总净利润。

1.2 数学模型

1.2.1 参数及变量说明

(1)模型标引及参数

(2)决策变量

yj为二进制变量，如果订单j被接受，yj为1，否则为0；xj,[k]为二进制变量，如果订单j被接受并分配至调度序列的第k个位置，xj,[k]为1，否则为0；Cj,s为订单j第s道工序的完工时间；C[k],s为订单序列第k个位置订单第s道工序的完工时间；Tj为订单j的拖期时间，Tj:=max{0,Cj,6-d}；A[k],s为订单调度序列第k个位置第s道工序的累计完工时间；D[k],s为订单调度序列第k个位置第s道工序的累计工作天数。

1.2.2 混合整数非线性规划模型

以最大化净利润为目标，可建立OAS_PPE优化模型如下:

优化目标:

(13)

其中，式(1)表示模型的目标为最大化总净利润；式(2)定义订单的拖期时间，其中M为非常大的正常数；式(3)约束每个被接受的订单都分配至工件序列中的一个位置；式(4)限制每个调度序列位置最多被分配一个订单；式(5)计算累计工作天数；式(6)计算第k个位置订单在第s个阶段的累计完成时间，即串行情况下第k个位置订单在第s道工序的的最早完成时间；式(7)计算订单在调度序列第k个位置的订单第1，2，5，6道工序的完工时间，这四道工序均为可间断工序，若不能在规定的工作时间内完成，可将未完成的部分移至下一个阶段完成；式(8)计算调度序列第k个位置的订单在浇筑工序(第3道工序)的完工时间，由于浇筑工序的不可间断性，因此该工序若不能在包含加班的时间段内完成，则需推迟到下一个工作日进行；式(9)计算调度序列第k个位置的订单在养护工序(第4道工序)的累计完成时间。式(10)为养护工序，其具有不可中断性和并行性，并且不需人工看护，因此该工序完工时间计算有以下两种情况：若养护工序可在包含加班的时间内完成, 则完工时间即为该工序开工时间加处理时间。若养护工序在夜间完成，其完工时间视为下一个工作日的开始时间。式(11)～(13)定义了各决策变量的取值范围。需要指出的是，该模型中既包括连续变量又包括离散变量，需要对订单选择和订单调度进行集成决策。从目标函数角度看，含有变量乘积的形式；从约束角度看，该模型中既包括线性约束，也包括复杂的非线性约束，如式(5)～(8)。加之OAS_PPE问题本身固有的NP-难性，因此该模型难以利用现有优化软件进行直接求解。

2 算法

由于传统的预制构件生产调度或者流水车间调度方面的研究一般仅限于对机器上工件排序进行单一决策研究[13,14]，因此其相关调度算法很难直接应用到OAS_PPE问题上，在这种情况下需要根据问题特点设计特定算法。本节通过集成特定问题知识、构造启发式、局部搜索和破坏-构造机制，提出了一种有效的混合加速迭代贪婪搜索框架。基于该框架，结合后插入操作和前后混合式插入操作，提出了两种混合加速迭代贪婪搜索算法。

2.1 混合加速迭代贪婪搜索

本文所提出的混合加速迭代贪婪框架如算法1所示。其基本步骤如下：(1)通过构造启发式NEH算法[15]产生一个完整的订单调度序列作为初始解；(2)通过两阶段局部搜索方法改进初始解；(3)通过破坏和加速构造对当前解进行摄动；(4)对得到的新解再次利用两阶段局部搜索方法进行搜索得到新解。对步骤(3)和(4)交替运行直到满足终止条件。

算法1(混合加速迭代贪婪搜索)输入:实例数据和算法参数输出:构造性序列π∗和最优目标函数值TNR(π∗)1π0←初始解2π∗←TLS(π0)%利用算法33对π∗执行破坏策略,即从π∗中随机选择d个订单组成πd;πR则为除去d个订单后剩余的订单组成的调度序列4πR←利用加速构造策略在πR的最佳位置插入πdi使目标值TNR最大5π2←TLS(πR)%利用算法36如果TNR(π∗)

下面针对构造启发式、两阶段局部搜索以及破坏和构造机制等关键部件进行介绍。

(1)构造启发式产生初始解

通过构造启发式NEH算法(算法2)产生一个较好的完整的订单调度序列作为初始解。

算法2(初始解的产生)输入:实例数据和算法参数输出:构造性序列π0和其所对应目标值TNR(π0)1pj=∑s∈kpj,s2设置π1←Ф,π2←Ф,πa←Ф,πb←Ф,πc←Ф,πd←Ф3π1←(πp1,…,πpj,…,πpJ),一批订单按Pj非递增排序π2←(πQ1,…,πQj,…,πQJ),一批订单按Qj非递减排序4πa←(πp1,πp2),πb←π1πaπc←(πQ1,πQ2),πd←π2πc5πa←在πa的最佳位置插入πbj使得TNR值最大πc←在πc的最佳位置插入πdj使得TNR值最大6如果TNR(πa)>TNR(πc),则π0←πa否则π0←πc7返回π0,TNR(π0)

(2)两阶段局部搜索

为提高个体局部搜索能力，设计了基于交换操作的两阶段局部搜索方法(算法3)，包括订单交换阶段和订单回插阶段。在订单交换阶段，调度序列中随机选择两个订单进行交换操作，通过判断交换后的序列中每个订单完成时间是否超过截止日期，确定接受集与拒绝集。与传统局部搜索不同的是，本文局部搜索基于OAS问题特点，在执行交换操作之后，并不直接进行目标函数评估，而是进一步将拒绝集的订单逐步插入到使TNR最大位置的接受集中，并与初始序列目标值比较，我们将该阶段简称为回插阶段。以上过程重复进行，直至局部搜索达最大迭代次数。

算法3两阶段局部搜索输入:实例数据,算法参数,一组订单序列π=(π1,π2,…,πj,…,πJ),最大迭代次数Iter输出:最优解π∗和最优目标函数值TNR(π∗)1π∗←初始解2在调度序列π∗随机选择两个位置的订单进行交换生成一个新的序列π1=(π1′,π2′,…,πk′,…,πJ′)3设置πa←Ф和πr←Ф4计算π1中πk′的完工时间C[k]5如果C[k]TNR(π∗),则π∗←πa8返回π∗,TNR(π∗)

(2)破坏和加速构造机制

在迭代贪婪算法中，从序列π*中随机抽取d个订单组成订单抽取序列πd。抽取订单后剩余的订单序列为πR。在传统IG算法[13,14]的构造阶段，需将破坏订单集合πd中的订单依次插入剩余订单集合πR的所有位置并计算目标值以便找出最佳插入位置，由于此过程需遍历πR的所有位置，因此该操作是导致IG算法运行效率降低的主要原因之一。为克服该困难，首先给出如下性质：

性质1在一个订单序列π=(π1,π2,…,πk,…,πJ)中，如果在第[k]个位置的订单完工时间超过其截止日期，则该订单插入到当前位置之后的所有位置均会超过截止日期，因此被拒绝。

利用该性质可得加速构造策略1如下：

基于性质1和2可得加速构造策略2如下：

加速构造策略2(Speedup Strategy 2, SS2)：在HIG算法重构造阶段，将某个订单j插到剩余订单集合的最后一个位置[k]构成新的调度序列。若满足≥C[k],6,则停止将此订单插入到这组订单排列顺序的其它位置。若不满足，则执行加速构造策略1。

基于迭代贪婪搜索框架，分别结合SS1和SS2提出了两种迭代加速贪婪搜索算法，在这里命名为HIG_SS1和HIG_SS2。采用传统构造方法的混合迭代贪婪搜索算法命名为HIG。在下一节中，我们将验证它们的有效性。

3 实验仿真与结果分析

3.1 算例生成与算法参数设置

订单数目J从集合{20, 30, 50, 70}中选取。为保证订单的多样性和差异性，针对不同规模订单，不同种类预制构件各随机生成10个不同组合的算例。各个生产阶段的处理时间及拖期惩罚采用文献[1]中的测试数据。本文算法基于Matlab 2016a在处理器Intel(R) Core (TM) i7-8550U CPU @1.80 GHZ 199GHZ内存为8GB的个人计算机上实现。为便于比较算法，我们还分别设计了适用于OAS_PPE问题的GA、TS和HGA_TS。其中HGA_TS算法是将遗传算法搜索到的相对较好解作为禁忌算法的初始解进行寻优，通过两种算法的交替迭代进行解的更新。通过田口方法调节算法参数，优化后的各算法参数如表1所示。其中d为破坏阶段抽取工件个数；TL为禁忌表长度；α为HGA_TS中GA与TS运行时间占比；SN为邻域长度；PS为种群规模；pc与pm分别为交叉率与变异率。

表1 算法参数设置

3.2 算法对比分析

本文中，不同规模的订单各取十组算例，每组算例运行20次。对于同一规模算例，为公平比较，所有算法均采用相同的运行时间。由于传统预制构件生产调度问题多以GA作为求解方法，因此本文以GA为基准算法，定义相对GA改进率如下：

运用上式，可以针对某一算例l计算各算法相对于GA的改进率。

表2给出了不同订单规模情况下不同算法相对于GA的平均改进率,即对某一规模的10个算例的改进率取平均值。由表2和图1可以看出，与GA,TS和HGA_TS相比，HIG_SS1，HIG_SS2以及HIG具有较为明显的改进，尤其是HIG_SS2,在订单数为20，30和50时，平均改进率最大，而HIG_SS1则在订单数为70时，平均改进率最大。相对于GA,HIG_SS1的综合改进率达到了6.77%(见表2最后一行)。换句话说，如果用遗传算法优化可以得到10万元的总净利润，利用HIG_SS1可以额外平均增加6770元的利润。从表2和图1还可以看出，带有加速构造策略的两种算法(HIG_SS1和HIG_SS2)明显优于不带加速构造策略的算法HIG，说明加速构造策略在相同运行时间情况下可以有效改善混合迭代贪婪算法求解质量。

表2 各算法相对于GA的平均改进率(%)

3.3 加速构造搜索策略有效性验证

为验证两种加速构造策略的有效性，对于同一规模算例，所有算法均在相同迭代次数下对运算时间进行对比。使用运行时间改进率(IR，Improved Ratio)来评估算法性能。具体如下：

IR=(RHTGi-RTHIG_SSi)×100/RTHIGi

其中,RTHIGi表示HIG算法在各规模实例上的平均运行时间，RTHIG_SSi表示具有加速构造策略i的算法在各规模实例上的平均运行时间。

表3给出了相同迭代次数下HIG、HIG_SS1和HIG_SS2三种算法的计算结果。从表3可以看出，与无加速构造策略的算法HIG相比，HIG_SS1和HIG_SS2两种算法在20个不同的算例中均有17个算例获得了运行效率的改进, 占比90%。如图2所示，对于不同规模的订单数，HIG_SS1的运行时间相较于HIG的运行时间改进率分别为2.09%、5.83%、4.29%和4.96%。而HIG_SS2相较于HIG的运行时间改进率分别为5.65%、7.88%、5.41%和5.97%。由此可见，加速构造策略1和2均具有良好的加速性能。同时，由表3和图2可知，在最大值，平均值，标准差基本相同情况下，对于所有订单规模，HIG_SS2的整体加速效果均优于HIG_SS1。

表3 相同迭代次数下HIG,HIG_SS1和HIG_SS2计算结果

3.4 加速构造策略收敛性验证分析

图3为不同规模问题情况下HIG、HIG_SS1和HIG_SS2三种算法的收敛曲线，其中横轴表示迭代次数，纵轴表示迭代次数对应的最大净利润TNR。如图3所示，三种算法在不同规模下均迅速收敛。随着迭代次数的增加，HIG_SS2在20、50和70规模订单的算例时收敛速度最快，且解的质量最好，50规模时其收敛曲线在20代后均趋于平稳。而HIG_SS1在30规模订单的算例时收敛速度较快，且解的质量最好。

4 结语

本文研究了公共交货期情形下预制构件生产环境中的订单接受与调度集成问题，建立了非线性混合整数数学规划模型。鉴于该问题复杂性，通过集成特定问题性质、构造启发式以及邻域搜索方法和破坏-构造机制，提出了一种基于加速构造策略的混合迭代贪婪搜索框架。基于两种调度序列插入操作性质，进而提出了两种混合加速迭代贪婪搜索算法(HIG_SS1和HIG_SS2)以提升算法运行效率，计算结果显示，与GA，TS和HGA_TS相比，HIG_SS1和HIG_SS2具有更好的求解质量和鲁棒性。同时验证了两种加速构造策略均能提升算法运行效率。与HIG相比，HIG_SS1和HIG_SS2算法收敛均较快，而且在相同的运行时间内，它们具有更好的平均求解质量。未来研究可以考虑将具有加速构造策略的混合迭代贪婪算法扩展至更为复杂的预制构件生产调度环境，比如分布式预制构件生产调度系统，不确定条件下的预制生产调度系统等。