D0I:10.13374/i.issnl00113.2009.10.024 第31卷第10期 北京科技大学学报 Vol.31 No.10 2009年10月 Journal of University of Science and Technology Beijing 0ct.2009 带组换装时间的单机调度问题 刘振刚)王道平)金 锋) 1)北京科技大学经济管理学院，北京1000832)清华大学自动化系，北京100084 摘要在某钢铁线材企业的实际调度问题的基础上，研究了一类带有组换装时间的单机调度问题·根据该调度问题的实际 需求，以最小化作业的最大延迟为优化目标·由于该问题是NP难的，提出了一类启发式算法来求解该问题，并进一步通过引 入问题的性质，提高算法的寻优性能，降低算法运行时间，该算法在随机产生的测试问题和企业的实际调度上均进行了测试， 实验结果表明该启发式算法能在短时间内获取近优解 关键词单机调度：组换装时间：延迟；启发式算法 分类号F224.3 Single machine scheduling problem with family setup times LIU Zheng"gang）,WANG Doo-ping）,IIN Feng 1)School of Economics and Management,University of Science and Technology Beijing.Beijing 100083.China 2)Department of Automation.Tsinghua University,Beijing 100084.China ABSTRACI A single machine scheduling problem with family setup time was studied to solve the real-life scheduling problem in a steel wire factory.According to the requirements of the real problem,the maximum lateness was minimized.As the problem is NP- hard,a heuristic algorithm was proposed to solve the problem.The problem's characteristics were introduced into the algorithm to improve the search efficiency and running time.The proposed algorithm was tested both on randomly generated problems and on real- life scheduling problems from the workshop.The results show that the proposed algorithm can obtain a near optimal solution in a short time. KEY WORDS single machine scheduling:family setup time:lateness:heuristic algorithm 随着中国经济的发展，钢铁线材的需求日益增 末，调度员会收到下月的生产订单（作业），作业可 加，钢铁线材企业的生产规模也越来越大·但是，在 按待加工线材的直径划分成不同的组.机器依次加 大多数钢铁线材企业中，生产调度（排程）依然主要 工两个同一直径（即同一个组）的作业时，中间不需 依靠人工完成，随着生产规模的增大，制订一个可 要切换工具，因此不需要换装时间(setup time);但 行的生产计划所耗费的时间越来越长，计划的有效 当机器加工两个不同直径（即不同组）的作业时，中 性也越来越难保证，以致生产订单拖期的情况频繁 间需要切换工具，因此需要相应的换装时间.该种 发生，降低了企业的市场竞争力，因此，为线材企业 换装时间称为组换装时间，此外，换装时间依赖于 提供一种快速而有效生产调度算法是一个亟待解决 前后两个作业组的先后顺序(sequence dependent), 的问题 这使得问题更为复杂， 本文在包头某线材企业实际调度问题的基础 该类问题的难点在于机器利用率和交货期是冲 上，研究了一类带组换装时间的单机调度问题.该 突的，若希望提高机器利用率，则会倾向于把同一 调度问题描述如下：企业加工线材的设备可看成一 个组的作业连续加工，以减少换装次数，但这样往往 台机器，该机器能加工不同直径的线材，在每个月 会使得某一个组的作业占用时间过长，从而导致其 收稿日期：2009-02-25 基金项目：国家自然科学基金资助项目(N。:70872010) 作者简介：刘振刚(1968一)，男，博士研究生；王道平(1964一)，男，教授，博士生导师，Emai:dpwang@manage,ustb:ed:cm
带组换装时间的单机调度问题 刘振刚1） 王道平1） 金 锋2） 1） 北京科技大学经济管理学院北京100083 2） 清华大学自动化系北京100084 摘 要 在某钢铁线材企业的实际调度问题的基础上研究了一类带有组换装时间的单机调度问题．根据该调度问题的实际 需求以最小化作业的最大延迟为优化目标．由于该问题是 NP 难的提出了一类启发式算法来求解该问题并进一步通过引 入问题的性质提高算法的寻优性能降低算法运行时间．该算法在随机产生的测试问题和企业的实际调度上均进行了测试 实验结果表明该启发式算法能在短时间内获取近优解． 关键词 单机调度；组换装时间；延迟；启发式算法 分类号 F224∙3 Single machine scheduling problem with family setup times LIU Zheng-gang 1）W A NG Dao-ping 1）JIN Feng 2） 1） School of Economics and ManagementUniversity of Science and Technology BeijingBeijing100083China 2） Department of AutomationTsinghua UniversityBeijing100084China ABSTRACT A single machine scheduling problem with family setup time was studied to solve the rea-l life scheduling problem in a steel wire factory．According to the requirements of the real problemthe maximum lateness was minimized．As the problem is NP－ harda heuristic algorithm was proposed to solve the problem．T he problem’s characteristics were introduced into the algorithm to improve the search efficiency and running time．T he proposed algorithm was tested both on randomly generated problems and on rea-l life scheduling problems from the workshop．T he results show that the proposed algorithm can obtain a near optimal solution in a short time． KEY WORDS single machine scheduling；family setup time；lateness；heuristic algorithm 收稿日期：20090225 基金项目：国家自然科学基金资助项目（No．70872010） 作者简介：刘振刚（1968－）男博士研究生；王道平（1964－）男教授博士生导师E-mail：dpwang＠manage．ustb．edu．cn 随着中国经济的发展钢铁线材的需求日益增 加钢铁线材企业的生产规模也越来越大．但是在 大多数钢铁线材企业中生产调度（排程）依然主要 依靠人工完成．随着生产规模的增大制订一个可 行的生产计划所耗费的时间越来越长计划的有效 性也越来越难保证以致生产订单拖期的情况频繁 发生降低了企业的市场竞争力．因此为线材企业 提供一种快速而有效生产调度算法是一个亟待解决 的问题． 本文在包头某线材企业实际调度问题的基础 上研究了一类带组换装时间的单机调度问题．该 调度问题描述如下：企业加工线材的设备可看成一 台机器该机器能加工不同直径的线材．在每个月 末调度员会收到下月的生产订单（作业）．作业可 按待加工线材的直径划分成不同的组．机器依次加 工两个同一直径（即同一个组）的作业时中间不需 要切换工具因此不需要换装时间（setup time）；但 当机器加工两个不同直径（即不同组）的作业时中 间需要切换工具因此需要相应的换装时间．该种 换装时间称为组换装时间．此外换装时间依赖于 前后两个作业组的先后顺序（sequence dependent） 这使得问题更为复杂． 该类问题的难点在于机器利用率和交货期是冲 突的．若希望提高机器利用率则会倾向于把同一 个组的作业连续加工以减少换装次数但这样往往 会使得某一个组的作业占用时间过长从而导致其 第31卷 第10期 2009年 10月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．31No．10 Oct．2009 DOI:10．13374／j．issn1001－053x．2009．10．024
,1348 北京科技大学学报 第31卷 他组的作业拖期；若以交货期为准则进行调度，则会 延迟时间，那么该调度方案的最大延迟时间可表示 倾向于先调度交货期紧的作业，但这样会导致很多 为Lmx（T)=max1≤≤F,1≤≤NU)Li(π)}.显然， 的换装次数，降低了机器利用率，也最终会导致作业 这N个作业的任意一个排列就构成了一个调度方 拖期.由于这个内在的矛盾，使得该问题非常难以 案，该问题的解空间大小为N!,若用Ⅱ来表示所 求解.该类问题已经被证明为NP难问题山 有解的集合，那么在本问题中，要寻找一个调度方案 该类带组换装时间的问题不但在钢铁线材行业 π*，使得Lm(x*)=min Lmax(π)|π∈Ⅱ} 出现，在其他行业也很常见，例如，染印行业，当染 图1给出了一个简单问题的调度方案.在该问 缸从染一个颜色的作业换到染另外一个颜色的作业 题中，共有六个作业，被划分为两个组.把调度方案 时，便需进行相应的染缸清洗时间，清洗时间的特 中连续加工的同一个组的作业，称为一个批次，如 性与本问题的组换装时间非常类似，因此，研究带 在图1的调度方案中，形成了三个批次，批次和批 组换装时间的调度问题具有非常重要的理论意义和 次之间，需要序相关的组换装时间， 实际应用价值 (2.1)22)(12)(1.1)1.3)☐ 23) 在该类问题上，已有不少理论研究，主要集中在 精确算法（动态规划算法和分枝定界算法），Monma 图1一个简单问题的调度方案 和Potts!提出了一种通用的动态规划方法，他们也 Fig-1 Scheduling of a simple problem 证明了该问题即使在组换装时间在序不相关 先回顾一下该问题的一个非常重要的性质，将 (sequence independent)的情况下也是NP难的. 该性质引入到本文提出的算法，以提高算法寻优性 Ghosh和Gupta)在他们基础上，提出了一种后向 能，减少算法运行时间， 动态规划方法，在一定程度上，降低了算法复杂度， 性质1]对于最小化Lmx的带组换装时间的 但是，这两种算法的复杂度都随作业数指数增长· 单机调度问题，必定存在一个满足如下性质的最优 Schutten等在原问题的基础上，考虑了不同的就 解：在该解中，来自同一个组的作业按照交货期非减 绪时间(release time),提出了一种分枝定界方法. (EDD)的顺序排列 Hariri和Potts也提出了一种分枝定界的方法，最 性质1等价于：若在某个解π中，有两个来自 大能求解50个作业的问题，由于精确算法（包括上 同一个组的作业(f,)和(f,j)满足d:<d但 述动态规划法和分枝定界法)的算法复杂度都是指 (f,)在(f,)之后加工，那么必定能找到另外一个 数增长的，无法求解实际问题，因此不少学者也研究 解元，在π'中，(f,i)在（f,j)之前加工且 启发式算法.Baker]针对组换装时间序不相关的 Lma(π)≤Lmx(π)·性质1还意味着，在同一个批 问题，提出了两种启发式算法.Baker和Magazinel) 次中的作业（显然来自同一个组）应该按照交货期非 以及Ji等[8]进一步研究了问题的结构性质，并提 减的顺序排列，若两个来自同一个组的作业处在不 出了一种最优算法，在算法中，他们利用问题性质 同批次中，那么他们也应该满足交货期非减. 构建组合作业和计算问题下界，以加快算法寻优速 根据性质1，可以将搜索空间丛N!缩小到 度.Potts和Kovalyov[9和Allahverd山i等o就该类 N/(N1N2…N)·这将大大提高算法的寻优性 问题做了非常好的综述 能和运算速度， 1问题描述和已有性质 2启发式算法 已知有N个作业要在一台机器上加工，这些作 业可被划分为F个组.设在第f(f=1,2,…,F)个 在现有的调度算法中，虽然不少算法非常有效， 组有八个作业，记为(f,1),（f,2),…,（f, 但往往原理复杂，运行时间较长，不易为实际生产调 N)·设作业(f,)的加工时间为p,交货期为 度人员接受.因此，本文提出一种原理简单且能在 短时间内找到近优解的启发式算法，该启发式算法 dr,对于连续加工的两个作业(f,i)和(g,j),若 与NEH算法思想类似(NEH算法虽然流程简单，但 这两个作业来自同一个组（即∫=9），那么两者之间 被公认为是求解流水线调度问题最实用的方法)， 不需要换装时间，否则需要换装时间s·不失一般 该启发式算法框架可描述如下. 性，假设组换装时间满足sg十sgh≥sfh· 在一个调度方案π中，用C:(π)和L:(x)= 2.1启发式算法1：HA1 C:(π)一d:分别来表示作业(f,i)的结束时间和 步骤1将作业按照EDD规则排列；若两个作
他组的作业拖期；若以交货期为准则进行调度则会 倾向于先调度交货期紧的作业但这样会导致很多 的换装次数降低了机器利用率也最终会导致作业 拖期．由于这个内在的矛盾使得该问题非常难以 求解．该类问题已经被证明为 NP 难问题［1］． 该类带组换装时间的问题不但在钢铁线材行业 出现在其他行业也很常见．例如染印行业当染 缸从染一个颜色的作业换到染另外一个颜色的作业 时便需进行相应的染缸清洗时间．清洗时间的特 性与本问题的组换装时间非常类似．因此研究带 组换装时间的调度问题具有非常重要的理论意义和 实际应用价值． 在该类问题上已有不少理论研究主要集中在 精确算法（动态规划算法和分枝定界算法）．Monma 和 Potts ［2］提出了一种通用的动态规划方法他们也 证 明 了 该 问 题 即 使 在 组 换 装 时 间 在 序 不 相 关 （sequence independent ） 的情况下也是 NP 难 的． Ghosh 和 Gupta ［3］ 在他们基础上提出了一种后向 动态规划方法在一定程度上降低了算法复杂度． 但是这两种算法的复杂度都随作业数指数增长． Schutten 等［4］在原问题的基础上考虑了不同的就 绪时间（release time）提出了一种分枝定界方法． Hariri 和 Potts ［5］也提出了一种分枝定界的方法最 大能求解50个作业的问题．由于精确算法（包括上 述动态规划法和分枝定界法）的算法复杂度都是指 数增长的无法求解实际问题因此不少学者也研究 启发式算法．Baker ［6］ 针对组换装时间序不相关的 问题提出了两种启发式算法．Baker 和 Magazine ［7］ 以及 Jin 等［8］进一步研究了问题的结构性质并提 出了一种最优算法．在算法中他们利用问题性质 构建组合作业和计算问题下界以加快算法寻优速 度．Potts 和 Kovalyov ［9］ 和 Allahverdi 等［10］ 就该类 问题做了非常好的综述． 1 问题描述和已有性质 已知有 N 个作业要在一台机器上加工这些作 业可被划分为 F 个组．设在第 f （ f ＝12…F）个 组有 Nf 个作业记为（ f1）（ f2）…（ f Nf）．设作业（ fi）的加工时间为 pif交货期为 dif．对于连续加工的两个作业（ fi）和（ gj）若 这两个作业来自同一个组（即 f＝g）那么两者之间 不需要换装时间否则需要换装时间 sf g．不失一般 性假设组换装时间满足 sf g＋sgh≥sfh． 在一个调度方案 π中用 Cf i（π）和 L f i（π）＝ Cf i（π）－ df i分别来表示作业（ fi）的结束时间和 延迟时间那么该调度方案的最大延迟时间可表示 为 L max（π）＝max1≤ f≤F1≤ i≤ N（ f）｛L f i（π）｝．显然 这 N 个作业的任意一个排列就构成了一个调度方 案该问题的解空间大小为 N！．若用 Π来表示所 有解的集合那么在本问题中要寻找一个调度方案 π∗使得 L max（π∗）＝min｛L max（π）｜π∈Π｝． 图1给出了一个简单问题的调度方案．在该问 题中共有六个作业被划分为两个组．把调度方案 中连续加工的同一个组的作业称为一个批次．如 在图1的调度方案中形成了三个批次．批次和批 次之间需要序相关的组换装时间． 图1 一个简单问题的调度方案 Fig．1 Scheduling of a simple problem 先回顾一下该问题的一个非常重要的性质．将 该性质引入到本文提出的算法以提高算法寻优性 能减少算法运行时间． 性质1［6］ 对于最小化 L max的带组换装时间的 单机调度问题必定存在一个满足如下性质的最优 解：在该解中来自同一个组的作业按照交货期非减 （EDD）的顺序排列． 性质1等价于：若在某个解 π中有两个来自 同一个组的作业（ fi）和（ fj ）满足 df i ＜ df j但 （ fi）在（ fj）之后加工那么必定能找到另外一个 解 π′在 π′中（ fi ） 在 （ fj ） 之 前 加 工 且 L max（π′）≤ L max（π）．性质1还意味着在同一个批 次中的作业（显然来自同一个组）应该按照交货期非 减的顺序排列若两个来自同一个组的作业处在不 同批次中那么他们也应该满足交货期非减． 根据性质1可以将搜索空间丛 N！缩小到 N！／（ N1N2… Nf ）．这将大大提高算法的寻优性 能和运算速度． 2 启发式算法 在现有的调度算法中虽然不少算法非常有效 但往往原理复杂运行时间较长不易为实际生产调 度人员接受．因此本文提出一种原理简单且能在 短时间内找到近优解的启发式算法．该启发式算法 与 NEH 算法思想类似（NEH 算法虽然流程简单但 被公认为是求解流水线调度问题最实用的方法）． 该启发式算法框架可描述如下． 2∙1 启发式算法1：HA1 步骤1 将作业按照 EDD 规则排列；若两个作 ·1348· 北 京 科 技 大 学 学 报 第31卷
第10期 刘振刚等：带组换装时间的单机调度问题 .1349. 业交货期相等，则加工时间长的作业优先，记排序 记将性质1引入算法HA1后的新算法为HA2.算 后的作业为J,,…,严 法HA2可描述如下， 步骤2调度前两个工件」和了，评估其可能 2.2启发式算法2：HA2 形成的两个部分解，取Lma最小的那个， 步骤1与步骤2同HA1. 步骤3对作业广，=3,4，…，n. 步骤3对作业，i=3,4,…,n, 步骤3.1将插入到已有部分解的第k个位 步骤3.0在已有部分解中，寻找与同一个 置(k=1,2,…,i),形成i个新的部分解 组且交货期仅次于的作业，记其位置为；若下 步骤3.2评估形成的i个新的部分解，取 是所在组的第1个作业，那么令1=一1. Lmx最小的那个作为下一个循环的部分解 步骤3.1将插入到已有部分解的第k个位 在上述流程中，步骤3最为关键，但原理非常简 置(k=l十1,2，，i),形成的(i一l)个新的部 单.如当=4时，已有部分解显然已含有三个工 分解 件，第4个工件」可插入到该部分解的第1、第2、 步骤3.2评估形成的i一L个新的部分解，取 第3及最后一个位置，在新形成的四个部分解中取 Lma最小的那个作为下一个循环的部分解. Lmx最小的那个进入下一轮循环 3性能测试 在步骤3的第i次循环中，需评估i个部分解 (每个部分解含i个作业)，由于评估一个含有i个 用VC十十实现了本文提出的两种算法(HA1 作业的部分解的算法复杂度为O(),第i次循环的 和HA2),为评估算法性能，还实现了文献[3]中的 算法复杂度为0(2).因此，对于一个含有n个作 动态规划方法(dy namic programming,DP)方法，用 业的问题，该算法的时间复杂度为O(n3),尽管这 以求解问题的最优解，所有算法均在Pentium4 已经是一个多项式复杂度的算法，但当n增大时， (2.6Gz)、512M内存的计算机上进行测试，对不 算法运行时间仍然会迅速增长，因此，笔者考虑将 同的作业数，共随机产生了720个问题进行测试. 该问题的性质引入到算法中，以提高算法寻优性能 表1列出了三种算法(DP,HA1和HA2)在随 和运算时间 机问题上的性能（已将数据根据作业数汇总），其中 显然，在步骤3中，同一个组的交货期大的作业 最优解率为算法能获得最优解的问题数与总问题数 有可能插入到交货期小的作业前面，因此在步骤 之比.与DP算法所得的解（即最优解）相比，HA1 3.2所得的i个部分解并不都满足性质1的最优性 算法和HA2算法能在不超过0.1s的时间内，在超 原则，因此，在步骤3的第i次循环中，设了是与作 过总问题数的1/3（约35%）的问题上获得最优解， 业∫同一个组且交货期仅次于的作业，由于」， 在大多数问题上也能获得近优解，若将HA1与 了，…，严已按照EDD规则排列，作业了在前i一1 HA2相比，则可以看出HA2不仅能获得比HA1更 次循环中已经排定，因此可以考虑将作业∫插入到 好的解，所需的运行时间也大大减少，这是因为在 作业了之后的所有位置，这样大大减少部分解的数 HA2中引入了问题的性质，使得HA2搜索的解始 量，又能保证产生的部分解满足性质1的最优性， 终保持性质1要求的最优性. 表1各算法在随机问题上的性能比较 Table I Performance comparison of algorithms on random problems 最大延迟Lmm CPU时间/ms 最优解率/% 作业数 DP HAI HA2 DP HAI HA2 HAI HA2 50 637 850 845 105 15 36.7 36.9 60 728 991 983 244 25 4 38.1 38.9 70 783 1092 1081 522 38 6 33.6 34.2 80 891 1277 1265 1001 54 9 33.9 34.4 90 978 1411 1401 1741 75 11 34.7 35.6 100 1073 1552 1537 2871 101 14 32.8 33.1 平均 848 1196 1185 1081 51 8 35.0 35.5
业交货期相等则加工时间长的作业优先．记排序 后的作业为 J 1J 2…J n． 步骤2 调度前两个工件 J 1 和 J 2评估其可能 形成的两个部分解取 L max最小的那个． 步骤3 对作业 J ii＝34…n． 步骤3∙1 将 J i 插入到已有部分解的第 k 个位 置（ k＝12…i）形成 i 个新的部分解． 步骤3∙2 评估形成的 i 个新的部分解取 L max最小的那个作为下一个循环的部分解． 在上述流程中步骤3最为关键但原理非常简 单．如当 i＝4时已有部分解显然已含有三个工 件第4个工件 J 4 可插入到该部分解的第1、第2、 第3及最后一个位置在新形成的四个部分解中取 L max最小的那个进入下一轮循环． 在步骤3的第 i 次循环中需评估 i 个部分解 （每个部分解含 i 个作业）．由于评估一个含有 i 个 作业的部分解的算法复杂度为 O（ i）第 i 次循环的 算法复杂度为 O（ i 2）．因此对于一个含有 n 个作 业的问题该算法的时间复杂度为 O（ n 3）．尽管这 已经是一个多项式复杂度的算法但当 n 增大时 算法运行时间仍然会迅速增长．因此笔者考虑将 该问题的性质引入到算法中以提高算法寻优性能 和运算时间． 显然在步骤3中同一个组的交货期大的作业 有可能插入到交货期小的作业前面因此在步骤 3∙2所得的 i 个部分解并不都满足性质1的最优性 原则．因此在步骤3的第 i 次循环中设 J′是与作 业 J i 同一个组且交货期仅次于 J i 的作业由于 J 1 J 2…J n 已按照 EDD 规则排列作业 J′在前 i－1 次循环中已经排定因此可以考虑将作业 J i 插入到 作业 J′之后的所有位置这样大大减少部分解的数 量又能保证产生的部分解满足性质1的最优性． 记将性质1引入算法 HA1后的新算法为 HA2．算 法 HA2可描述如下． 2∙2 启发式算法2：HA2 步骤1与步骤2 同 HA1． 步骤3 对作业 J ii＝34…n． 步骤3∙0 在已有部分解中寻找与 J i 同一个 组且交货期仅次于 J i 的作业记其位置为 l；若 J i 是所在组的第1个作业那么令 l＝－1． 步骤3∙1 将 J i 插入到已有部分解的第 k 个位 置（ k ＝ l ＋12…i）形成的（ i － l）个新的部 分解． 步骤3∙2 评估形成的 i－ l 个新的部分解取 L max最小的那个作为下一个循环的部分解． 3 性能测试 用 VC＋＋实现了本文提出的两种算法（HA1 和 HA2）为评估算法性能还实现了文献［3］中的 动态规划方法（dynamic programmingDP）方法用 以求解问题的最优解所有算法均在 Pentium 4 （2∙6GHz）、512M 内存的计算机上进行测试．对不 同的作业数共随机产生了720个问题进行测试． 表1列出了三种算法（DPHA1和 HA2）在随 机问题上的性能（已将数据根据作业数汇总）其中 最优解率为算法能获得最优解的问题数与总问题数 之比．与 DP 算法所得的解（即最优解）相比HA1 算法和 HA2算法能在不超过0∙1s 的时间内在超 过总问题数的1／3（约35％）的问题上获得最优解 在大多数问题上也能获得近优解．若将 HA1与 HA2相比则可以看出 HA2不仅能获得比 HA1更 好的解所需的运行时间也大大减少．这是因为在 HA2中引入了问题的性质使得 HA2搜索的解始 终保持性质1要求的最优性． 表1 各算法在随机问题上的性能比较 Table1 Performance comparison of algorithms on random problems 作业数 最大延迟 L max CPU 时间／ms 最优解率／％ DP HA1 HA2 DP HA1 HA2 HA1 HA2 50 637 850 845 105 15 3 36∙7 36∙9 60 728 991 983 244 25 4 38∙1 38∙9 70 783 1092 1081 522 38 6 33∙6 34∙2 80 891 1277 1265 1001 54 9 33∙9 34∙4 90 978 1411 1401 1741 75 11 34∙7 35∙6 100 1073 1552 1537 2871 101 14 32∙8 33∙1 平均 848 1196 1185 1081 51 8 35∙0 35∙5 第10期 刘振刚等： 带组换装时间的单机调度问题 ·1349·
.1350 北京科技大学学报 第31卷 4应用案例 5结论 在上述算法的基础上，为包头某线材厂设计开 本文在某线材企业实际调度问题的基础上，研 发了作业计划优化系统.该系统从企业已有的ERP 究了带组换装时间的单机调度问题，由于问题是 NP难的，本文提出了一种启发式算法，并进一步将 系统中获取生产数据（即作业的加工时间、交货期 等)，通过上述算法，优化自动生成作业计划，调度员 该问题的性质引入该算法，提高算法的寻优性能和 运算时间，算法在随机产生的问题和实际问题上进 在系统给出的计划基础上，稍作修改便可作为正式 计划下达，大大提高了计划编制的效率，也提高了计 行了测试，实验结果表明，提出的算法能在较短时间 划的质量，下面给出了具体应用效果的案例 内取得问题的近优解. 在今后的研究中，将进一步研究该问题的性质， 表2显示了包头该线材厂连续七个月的实际生 开发更高效的优化调度算法，解决实际企业问题 产数据，由于该线材厂每月做一次计划，因此共形 成七个调度问题，记为P1~P7,这些问题的基本信 参考文献 息（作业数及作业组数）见表2，从表2中可以看出， [1]Lu L F.Yuan J J.The single machine batching problem with identical family setup times to minimize maximum lateness is 这些问题的作业数和作业组数要比随机问题大得 strongly NP-hard.Eur J Oper Res.2007.177(2):1302 多，无法再用DP算法获取这些问题的最优解.因 [2]Monma C L.Potts C N.On the complexity of scheduling with 此，表2中仅列出了HA1和HA2的性能. batch setup times.Oper Res.1989.37(5):798 表2各算法在实际问题上的性能比较 [3]Ghosh JB.Gupta J N D.Batch scheduling to minimize maximum Table 2 Performance comparison of algorithms on real problems lateness.Oper Res Lett,1997.21(2):77 [4]Schutten J M J.Van deValde S L.Zijm W H M.Single machine 最大延迟Lmm CPU时间/ms 问题 scheduling with release dates,due-dates and family setup times. HAl HA2 HAl HA2 Manage Sci,1996,42:1165 Pl 130 12 87 82 1235 156 [5]Hariri A M A.Potts C N.Single machine scheduling with batch P2 84 10 57 咏 328 63 set up times to minimize maximum lateness.Ann Oper Res, 1997,70.75 76 9 99 99 250 47 [6]Baker K R.Heuristic procedures for scheduling job families with P4 137 10 127 127 1375 188 setups and due dates.Nav Res Logist,1999.46(8):978 P5 135 12 115 115 1891 281 [7]Baker K R.Magazine M J.Minimizing maximum lateness with P6 201 14 141 142 4734 641 job families.Eur JOper Res.2000.127(1):126 P7 87 13 158 158 390 109 [8]Jin F,Song J.Wu C.A simulated annealing algorithm for sin- gle machine scheduling problems with family setups.Comput Op 从表2中可以看出，对于实际问题HA2算法仍 er Res,2009,36(7):2133 [9]Potts C N,Kovalyov M Y.Scheduling with batching:a review- 然能够获得比HA1算法更好的解，而所需时间则比 ErJ0 per Res,2000,120(2):228 HA1算法要少得多，所有问题均能在不超过1s的 [10]Allahverdi A.Ng C T.Cheng T C E.et al.A survey of 时间内获得近优解，这个时间在实际生产过程中是 scheduling problems with setup times or costs.Eur Oper Res. 可以接受的. 2008,187(3):985
4 应用案例 在上述算法的基础上为包头某线材厂设计开 发了作业计划优化系统．该系统从企业已有的 ERP 系统中获取生产数据（即作业的加工时间、交货期 等）通过上述算法优化自动生成作业计划调度员 在系统给出的计划基础上稍作修改便可作为正式 计划下达大大提高了计划编制的效率也提高了计 划的质量．下面给出了具体应用效果的案例． 表2显示了包头该线材厂连续七个月的实际生 产数据．由于该线材厂每月做一次计划因此共形 成七个调度问题记为 P1～P7这些问题的基本信 息（作业数及作业组数）见表2．从表2中可以看出 这些问题的作业数和作业组数要比随机问题大得 多无法再用 DP 算法获取这些问题的最优解．因 此表2中仅列出了 HA1和 HA2的性能． 表2 各算法在实际问题上的性能比较 Table2 Performance comparison of algorithms on real problems 问题 N F 最大延迟 L max CPU 时间／ms HA1 HA2 HA1 HA2 P1 130 12 87 82 1235 156 P2 84 10 57 55 328 63 P3 76 9 99 99 250 47 P4 137 10 127 127 1375 188 P5 135 12 115 115 1891 281 P6 201 14 141 142 4734 641 P7 87 13 158 158 390 109 从表2中可以看出对于实际问题 HA2算法仍 然能够获得比 HA1算法更好的解而所需时间则比 HA1算法要少得多所有问题均能在不超过1s 的 时间内获得近优解这个时间在实际生产过程中是 可以接受的． 5 结论 本文在某线材企业实际调度问题的基础上研 究了带组换装时间的单机调度问题．由于问题是 NP 难的本文提出了一种启发式算法并进一步将 该问题的性质引入该算法提高算法的寻优性能和 运算时间．算法在随机产生的问题和实际问题上进 行了测试实验结果表明提出的算法能在较短时间 内取得问题的近优解． 在今后的研究中将进一步研究该问题的性质 开发更高效的优化调度算法解决实际企业问题． 参 考 文 献 ［1］ Lu L FYuan J J．The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard．Eur J Oper Res2007177（2）：1302 ［2］ Monma C LPotts C N．On the complexity of scheduling with batch setup times．Oper Res198937（5）：798 ［3］ Ghosh J BGupta J N D．Batch scheduling to minimize maximum lateness．Oper Res Lett199721（2）：77 ［4］ Schutten J M JVan deValde S LZijm W H M．Single machine scheduling with release datesdue-dates and family setup times． Manage Sci199642：1165 ［5］ Hariri A M APotts C N．Single machine scheduling with batch set-up times to minimize maximum lateness． A nn Oper Res 199770：75 ［6］ Baker K R．Heuristic procedures for scheduling job families with setups and due dates．Nav Res Logist199946（8）：978 ［7］ Baker K RMagazine M J．Minimizing maximum lateness with job families．Eur J Oper Res2000127（1）：126 ［8］ Jin FSong S JWu C．A simulated annealing algorithm for single machine scheduling problems with family setups．Comput Oper Res200936（7）：2133 ［9］ Potts C NKovalyov M Y．Scheduling with batching：a review． Eur J Oper Res2000120（2）：228 ［10］ Allahverdi ANg C TCheng T C Eet al．A survey of scheduling problems with setup times or costs．Eur J Oper Res 2008187（3）：985 ·1350· 北 京 科 技 大 学 学 报 第31卷