·530 工程科学学报，第41卷，第4期 绝则产生拒绝成本，若接受则必须安排生产，此时可 器限制的订单接受与调度模型如下： 能产生拖期成本，且每个订单具有不同的单位拖期 min F= 惩罚.此外，订单只允许在指定的机器集合中选择 A=A1-)回+A7 加工机器，且存在顺序与机器依赖的安装时间约束. (1) 问题要求确定被拒绝的订单集合以及被接受订单的 =0j=1,2…n (2) 调度方案，优化目标为最小化总拒绝成本和总拖期 ,台 成本之和 正如引言所述，己有文献所研究的订单接受与 ∑)0≤1，i=1,2,m,k=1,2,n（63) 不相关并行机调度在问题约束以及优化目标方面均 与本文存在差别，因此有必要建立问题的数学模型， 三X≤M月 对问题进行准确描述.本文问题是不相关并行机调 i=1,2,…,m,k=1,2,…,n-1 (4) 度的扩展问题，目标函数则是在总加权拖期这一经 C1-Pa-s-C+M(2-yk+)-y）≥0， 典调度目标的基础上增加了总拒绝成本.调度问题 j≠l,j,l=1,…,n,VieM nM, 的关键是确定机器上的工件（订单）加工序列，相应 k=1,2,…,n-1 (5) 的决策变量在模型中有两种基于0一1整型变量的 (6) 表示方式：一种是定义订单间的相对位置关系， C-∑y,≥0，j=1,2,n M,= 另一种则是定义订单在机器上的具体位置.安装时 T,≥0，j=1,2,…,n (7) 间约束下的不相关并行机调度多采用前一种表示方 T+M(1-x）≥C-d,j=1,2,…,n (8) 法，回，但后一种方法能更为直观的表示订单加工 y城=0，j,k=1,2,…,n,Hi∈{1,2，…，m}1M 序列，易于与算法中的编码方案相互转化（参见本 (9) 文第2节首段)，因此本文采用后一种方式建模.此 y继∈{0,1}，j,k=1,2,…,n,i∈M,(10) 外，考虑到本文问题还需要确定订单的接受决策，且 目标函数(1)表示最小化总成本，即总拒绝成 该决策仅有“接受”拒绝”两种状态，因此在模型中 本和总拖期成本之和.约束(2)表示若订单j被拒 引入0一1整型变量来表示订单的接受情况.具体建 绝则不允许加工，否则该订单必须且只能指派到一 模如下. 台可加工机器的一个位置上.约束(4)表示每个机 首先，为便于建模，定义以下符号 器位置至多允许安排一个订单；约束(4)表示机器 (1)索引与集合.m为机器数量：i为机器编号， 位置编号的连续性，若位置k未安排订单，则之后的 i=1,2,,m;n为订单数量：j为订单编号，j=1,2, 位置也不允许安排订单.约束(5)要求同一台机器 ·,n;k为机器的加工位置，表示在机器上第k个加 在同一时刻只允许加工一个订单，且紧邻订单之间 工的订单，1≤k≤n;M为订单j的可加工机器编号 存在顺序与机器依赖的安装时间.约束(6)限定了 集合. 订单的完工时间.约束(7)和(8)定义了订单拖期 (2)问题参数.P为订单j在机器i上的加工时 约束(9)为可加工机器限制，订单不允许被指派到 间；r©心；和d,为订单j的拒绝成本、单位拖期成本 不可加工的机器上.约束(10)为变量取值约束. 和交货期；s为订单j被指派到机器i且紧前订单为 此模型为混合整数线性规划(mixed integer lin- l时的安装时间；M为极大的正数. ear programming,MLP),前文也指出该问题是NP (3)决策变量.x为0-1变量，若订单j被接受 难的.针对这类问题，遗传算法等群智能算法是一 则为1，否则为0；y继为0-1变量，若订单j被指派到 种有效方法，且将问题特征引入算法中能够提高求 机器i的位置k上则为1，否则为0；C:为订单j的完 解质量.因此，本文将首先探讨问题的性质，进而结 工时间. 合问题性质设计算法 (4)决策变量的衍生变量.T:为订单j的拖期， 2基于调度的订单拒绝策略 T=max{C-d,0};F和f为总成本和订单j的成 本：若订单j被拒绝，则f=rej,否则f=w,T: 订单接受与调度是一类联合决策问题，令RS 表示拒绝订单集合，Ⅱ表示接受订单的调度方案， F- 则问题解可表示为决策对RS,Ⅱ).根据MP模 不相关并行机环境下具有安装时间和可加工机 型，RS和Ⅱ定义为：RS={jlx=0,j∈{1,2，，工程科学学报，第 41 卷，第 4 期 绝则产生拒绝成本，若接受则必须安排生产，此时可 能产生拖期成本，且每个订单具有不同的单位拖期 惩罚． 此外，订单只允许在指定的机器集合中选择 加工机器，且存在顺序与机器依赖的安装时间约束． 问题要求确定被拒绝的订单集合以及被接受订单的 调度方案，优化目标为最小化总拒绝成本和总拖期 成本之和． 正如引言所述，已有文献所研究的订单接受与 不相关并行机调度在问题约束以及优化目标方面均 与本文存在差别，因此有必要建立问题的数学模型， 对问题进行准确描述． 本文问题是不相关并行机调 度的扩展问题，目标函数则是在总加权拖期这一经 典调度目标的基础上增加了总拒绝成本． 调度问题 的关键是确定机器上的工件( 订单) 加工序列，相应 的决策变量在模型中有两种基于 0--1 整型变量的 表示方式［11］: 一种是定义订单间的相对位置关系， 另一种则是定义订单在机器上的具体位置． 安装时 间约束下的不相关并行机调度多采用前一种表示方 法［10，12］，但后一种方法能更为直观的表示订单加工 序列，易于与算法中的编码方案相互转化( 参见本 文第 2 节首段) ，因此本文采用后一种方式建模． 此 外，考虑到本文问题还需要确定订单的接受决策，且 该决策仅有“接受”“拒绝”两种状态，因此在模型中 引入 0--1 整型变量来表示订单的接受情况． 具体建 模如下． 首先，为便于建模，定义以下符号: ( 1) 索引与集合． m 为机器数量; i 为机器编号， i = 1，2，…，m; n 为订单数量; j 为订单编号，j = 1，2， …，n; k 为机器的加工位置，表示在机器上第 k 个加 工的订单，1≤k≤n; Mj 为订单 j 的可加工机器编号 集合． ( 2) 问题参数． pij为订单 j 在机器 i 上的加工时 间; rejj 、wj 和 dj 为订单 j 的拒绝成本、单位拖期成本 和交货期; silj为订单 j 被指派到机器 i 且紧前订单为 l 时的安装时间; M 为极大的正数． ( 3) 决策变量． xj 为 0--1 变量，若订单 j 被接受 则为 1，否则为 0; yijk为 0--1 变量，若订单 j 被指派到 机器 i 的位置 k 上则为 1，否则为 0; Cj 为订单 j 的完 工时间． ( 4) 决策变量的衍生变量． Tj 为订单 j 的拖期， Tj = max { Cj － dj ，0} ; F 和 fj 为总成本和订单 j 的成 本; 若 订 单 j 被 拒 绝，则 fj = rejj ，否 则 fj = wj Tj ; F = ∑ n j = 1 fj ． 不相关并行机环境下具有安装时间和可加工机 器限制的订单接受与调度模型如下: min F = ∑ n j = 1 fj = ∑ n j = 1 ( 1 － xj ) rejj + ∑ n j = 1 xj wj Tj ( 1) s． t． xj － ∑i∈Mj ∑ n k = 1 yijk = 0，j = 1，2，…，n ( 2) ∑ n j = 1 yijk≤1，i = 1，2，…，m，k = 1，2，…，n ( 3) ∑ n j = 1 yi，j，k + 1≤M ∑ n j = 1 yijk， i = 1，2，…，m，k = 1，2，…，n － 1 ( 4) Cl － pil － sijl － Cj + M( 2 － yil( k + 1) － yijk ) ≥0， j≠l，j，l = 1，…，n，i∈Mj∩Ml， k = 1，2，……，n － 1 ( 5) Cj － ∑i∈Mj ∑ n k = 1 yijk pij≥0，j = 1，2，…，n ( 6) Tj≥0，j = 1，2，…，n ( 7) Tj + M( 1 － xj ) ≥Cj － dj ，j = 1，2，…，n ( 8) yijk = 0，j，k = 1，2，…，n，i∈{ 1，2，…，m} \Mj ( 9) xj ，yijk∈{ 0，1} ，j，k = 1，2，…，n，i∈Mj ( 10) 目标函数( 1) 表示最小化总成本，即总拒绝成 本和总拖期成本之和． 约束( 2) 表示若订单 j 被拒 绝则不允许加工，否则该订单必须且只能指派到一 台可加工机器的一个位置上． 约束( 4) 表示每个机 器位置至多允许安排一个订单; 约束( 4) 表示机器 位置编号的连续性，若位置 k 未安排订单，则之后的 位置也不允许安排订单． 约束( 5) 要求同一台机器 在同一时刻只允许加工一个订单，且紧邻订单之间 存在顺序与机器依赖的安装时间． 约束( 6) 限定了 订单的完工时间． 约束( 7) 和( 8) 定义了订单拖期． 约束( 9) 为可加工机器限制，订单不允许被指派到 不可加工的机器上． 约束( 10) 为变量取值约束． 此模型为混合整数线性规划( mixed integer lin￾ear programming，MILP) ，前文也指出该问题是 NP 难的． 针对这类问题，遗传算法等群智能算法是一 种有效方法，且将问题特征引入算法中能够提高求 解质量． 因此，本文将首先探讨问题的性质，进而结 合问题性质设计算法． 2 基于调度的订单拒绝策略 订单接受与调度是一类联合决策问题，令 ＲS 表示拒绝订单集合，Π 表示接受订单的调度方案， 则问题解可表示为决策对〈ＲS，Π〉． 根据 MILP 模 型，ＲS 和 Π 定义为: ＲS = { j | xj = 0，j∈{ 1，2，…， · 035 ·