不同交货期时间窗下的平行机生产问题研究

杨婉琳，朱伏平

（西南科技大学制造科学与工程学院，四川 绵阳 621010）

1 引言

传统大规模生产逐渐出现定制化生产需求，在有限设备生产能力下，合理安排生产任务加工，高效、及时、动态规划生产排程，进行智能化生产调度成为众多企业的共同目标。生产排序问题研究，按有无交货期约束情况分为两类：一类无交货期约束[1-3]，另一类有交货期约束。对于无交货期约束情况，大部分研究者以时间表长最短、设备准备时间最短、等待时间最短等作为决策指标。如文献[4]以总订货提前期与总成本加权和最小化作为目标，禁忌搜索算法与动态规划算法相结合，研究订单分配、生产调度和分批运输调度三个阶段。在少量研究有交货期约束生产排序问题中，研究者多以交货期相同[5]情况作为研究对象，并假设生产任务是允许延误，以最长延误时间、总延误时间最短[6]等作为决策变量，建立基于算法基础的拖期惩罚隶属函数等。如文献[7]提出对模糊交货期Flow-shop调度问题机会约束设置惩罚函数，引进自适应变异和交叉方法改进算法；而生产任务交货期限不同的平行机生产排序问题，目前研究较少[8-10]。研究在订单交货期、到达时间等约束条件下平行机生产排序问题，提出在准时交货条件下“最小提前生产时间”，解决在优先考虑不同交货期约束下平行机生产排序问题。

2 问题描述和模型建立

j个任务在m台平行机上进行生产，任务集合为J=｛J1，J2，…Jj｝，机台集合为M=｛M1，M2，…Mm｝。m台平行机均可加工工厂任意产品，由于任务数量j远远大于机台数量m，并存在众多不可提前预知生产任务加工时间区间冲突，故该类问题为NP问题。

模型建立界定范围如下：

（1）面向订单生产方式，必须保证生产任务在交货期前完成，生产任务加工过程不可以中断；

（2）机台更换加工任务准备时间是一个常数δ，假设时间常数δ极小于加工时间，在生产排序中忽略常数δ影响；

（3）该系统不研究没有充足加工时间插单和急单问题；

（4）一个生产任务同时只可以在一个机台上完成，一个机台同时也只能加工一个生产任务；

（5）生产任务可以提前，但不允许延误。

下文中使用的符号定义，如表1所示。

表1 符号定义表Tab.1 Symbol Definition Table

模型建立需满足以下假设。假设1：每台平行机上加工作业应根据开始加工时间进行不减排列，即根据EST规则进行排列，每台机台上加工任务应不存在时间竞争。假设2：每个生产任务都必须被完成，并且每个加工任务都应在交货期前完成。假设3：上述模型问题，一定存在一个或多个提前加工时间最小的最优解。建立平行机生产排序求解最终模型。

式中：（1）—所有加工任务在客户要求交货期前完成；（3）—对于一个机台上所有加工任务，不存在加工时间竞争；（4）—一个加工任务仅能在一个机台上完成，并且每个加工任务都必须被机台加工。

3 算法设计

3.1 基于“虚拟订单”的组合策略

“虚拟订单”假定所有产品交货期一致，用于预测订单分布，以保证在产品机台组合时机台负荷均衡化、后期数据调整快速响应。下文中使用的符号定义，如表2所示。

以LPT（最长加工时间优先）为规则，（20～80）%原则作为约束条件，优化同速机不可中断极小化表长排序问题。

目标函数：Pm∥Cmax

（1）依排列结果进行百分比累计，累计百分比第一次出现大于或等于80%时停止百分比累计，即B1+B2+B3+…+Bn-1＜80%，B1+B2+…Bn-1+Bn≥80%，B1至Bn代表n种产品为“虚拟”订单中产品种类，得出虚拟订单集合 X=｛X1，X2，…Xn｝，Xn=（i，Pi，Δt）。

（2）任务按加工时间 Pi进行不减排列，即 An-1≥An，n=1，2，…n；

（3）当t=0时，取前m个任务依次排列在m台机台上，机台Mm上加工产品集合记为 Sm=｛a，b，…k∥a，b，…k∈（1，2，…i）｝，若任务Xn中产品i在机台Mm上加工，则称i∈Sm，Xn∈Mm；

（4）任务Xn排在机台Mm上，则机台负荷率Fm=Σi∈SmPi/Δt，检验是否Fm≥80%，若“是”则该机台饱和，退出可用机台集合；若“否”，则该机台仍存在于可用机台集合中；即：

（5）取剩余任务中加工时间最长任务（未加工任务中加工时间最长者）排在Fm最小机台上；

（6）重复步骤（4），重复步骤（5）；

（7）直到n个任务全部排完得出机台产品组合策略Dm。

表2 符号定义表Tab.2 Symbol Definition Table

3.2 加工任务在机台的分配

任务集合进入生产系统之后，根据机台产品组合策略D_m得出机台 m 加工任务集合 Sm=｛Ja，Jb，…Jk∥Ja，Jb，…Jk∈J｝，机台Mm的加工任务集合中生产任务均属于任务集合J=｛J1，J2，…Jj｝。设计基于ECT规则生产就绪时间可控提前的生产排序启发式算法。

（1）生产任务进入，依据产品机台组合Dm进行任务分派，在Dm中找不到生产机台的生产任务进入集合D中等待处理。机台Mm上生产任务即Sm中Jj按照交货期dj进行不减排序（ECT规则），在机台Mm上等待加工任务数记为k，排列ϖ=（ϖ1，ϖ2，…ϖk），存在 dϖ（n-1）≤dϖ（n），n=1，2，…k。

（2）针对Sm中不减排序生产任务 Jj，若存在任意 n 使得 dϖ（n-1）-dϖ（n）≤0，则任务 Jϖ（n）与任务 Jϖ（n+1）在机台 Mm上存在生产时间冲突，故将任务 Jϖ（n+1）从机台 Mm加工任务集合中删除，任务 Jϖ（n+1）进入集合 D 中等待安排。即：若 Jϖ（n）∈Sm，则∃∀n∈（1，2，…k）

（3）机台出现（2）情况，则转（4），若不出现，转（5）。

（4）删除重合加工任务Jϖ（n+1）后，根据 dj再次进行不减排序。重复步骤（2）。

（5）针对机台Mm初步生产任务安排完成，机台Mm上所有加工任务均不存在时间冲突，在机台无故障发生时候可以保证完成。整理集合D中加工任务，记集合D中加工任务数为k，则按照开始加工时间 r_j进行不减排序（EST 规则），排列 π=（π1，π2，…πk），即存在 rπ（n-1）≤rπ（n），n=1，2，…k。

（6）依次选取集合D中按加工开始时间排序的生产任务Jj，在众多机器中筛选出满足任务Jj需求时间区间空闲机器Mm，记机台Mm对任务Jj的接受能力为Nmj，Nmj=0可接受，Nmj=1不可接受。∃Jπ（n），Jπ（n+1）∈Sm则：

（7）Nj0为任务Jj可用机台集合，Nj1为任务Jj不可用机台集合。，则转至（8），若 N=Ø，则转至 2.3。j0

（8）在Nmj=0可接受机台Mm上与任务Jj开始时间rj最接近结束时间 dπ（n）生产任务称为 Jπ（n），记 Δχ=rj-dπ（n）。任务 Jj选择在 Δχ最小的机台上生产。即：minΔχ=rj-dπ（n），Nmj=0，Jπ（n）∈Sm⇒Jj∈Sm。

3.3 最小提前生产时间排序

（1）当Nj0=Ø，无机台可为生产任务Jj提供加工时间时，机台需调整生产任务安排，为保证所有产品在交货期前完成，将机台上生产任务提前。对于任意机台Mm上，存在加工任务Jπ（a），使Jπ（a）≤dj，Jπ（a+1）＞dj，则生产任务 Jπ（a）和 Jπ（a+1）之间空闲时间区间 θa=［da，ra+1］，a∈［1，k］。任务 Jj与任务 Jπ（a）之间时间区间记为 τa，为更好解决生产计划安排问题，进行分类归纳可得出：

（2）存在一个n使

（3）任务Jj提前投入生产时间记为Ej，则：

Ej=Ej

Ea=dj-rj-τa

Ea-1=dj-rj-τa-θa-1

Ea-n+1=dj-rj-τa-θa-1-…-θa-n+1

Ea-n=dj-rj-τa-θa-1-…-θa-n+1-θa-n

（4）机台Mm上加工任务提前生产时间总和记为Em，Em最小机台Mm即为任务Jj加工机台，机台Mm上加工任务Ja最终开始加工时间

（5）得出所有机台上生产任务集合Sm和生产计划Smr。

4 仿真案例实践

设计以下仿真案例实验，用MATLAB软件，随机抽取5台机台和25个生产任务进行仿真，对仿真结果进行评价。运行环境为：Windows10 64位操作系统，内存为4G。实验包括25个生产样本、5台可供选择机器，依据启发式算法规则进行仿真计算，最后输出结果为25个样本生产计划排程以及各机台占有率和利用率。使用上述最小提前生产时间算法得出生产排程，如表3所示。验证机台占用率和利用率充分说明该算法有效性和优越性，在不接受新生产任务和拒绝原生产任务硬性条件下，通过使用该算法，降低了机台平均占用率，提高了机台利用率，减少机台闲置，最大限度使用设备，各设备工作任务分配较为合理，如表4所示。

表3 生产任务排程Tab.3 The Production Task Scheduling

表4 算法数据对比表格Tab.4 Algorithm Data Contrast

5 结束语

研究企业在订单交货期、到达时间和设备产能资源等约束条件下平行机生产排序问题，以提高客户满意度、保证产品交货期为出发点；最小化订单提前生产时间作为目标，利用启发式规则构建虚拟订单进行产品组合，建立基于交货期约束系统求解模型；提出“最小提前生产启发式算法”进行求解，解决众多企业在优先考虑不同交货期约束下平行机实际生产调度问题；最后，使用仿真实验进行模型求解，验证了该方法可行性，以及在实际生产排程中优越性，该应用研究为进一步研究不同交货期时间窗下较大规模复杂平行机排序问题提供可鉴方法，填补交货期约束研究下部分空缺。研究问题中尚未准确考虑到紧急订单插单排序问题、供应链断链等情况，这些值得更进一步研究。