汽车维修车间作业排序的优化模型及调度算法.pdf

第2 7 卷第5 期 2 0 1 0 年5 月 计算机应用研究 A p p lica t io nR e s e a r cho fC o m p u t e r s V 0 1 2 7N o 5 M a y2 0 1 0 汽车维修车间作业排序的优化模型及调度算法木 杨琴1 2 ，周国华1 ，李艳茹2 ，赵茜2 ( 1 西南交通大学经济管理学院，成都6 1 0 0 3 1 ；2 四川师范大学商学院，成都6 1 0 0 6 8 ) 摘要：针对汽车维修车间调度缺乏科学规划，导致较长的客户等待时间和较低的设备利用率的问题，在结合 优化调度理论的基础上，对这一实际调度问题的特性、模型和算法进行了研究。首先从最小化目标、机器环境、 加工特征和约束几方面分析了问题的特征，建立了对应的数学模型；然后根据问题特性设计了分解法与约束引 导的启发式算法相结合的调度算法；最后以实例分析验证了算法的可行性。仿真结果表明了所用算法在优化目 标函数值上的优越性。 关键词：汽车维修车间；优化调度；基于工作的分解法；约束引导的启发式算法 中图分类号：F 4 0 6 2文献标志码：A文章编号：1 0 0 1 - 3 6 9 5 ( 2 0 1 0 ) 0 5 1 6 8 6 0 4 d o i：1 0 3 9 6 9 j is s n 1 0 0 1 - 3 6 9 5 2 0 1 0 0 5 0 2 1 O p t im a l m o d e lsa n ds ch e d u lin ga lg o r it h mo fa u t od e a le r s h ip Y A N GQ in l”，Z H O UG u o h u a l，L IY a h m 2 ，Z H A OX i2 ( 1 & h o d 矿E co n o m ics M a n a g e m e n t ，S o u t h w e s tJ ia o t o n g 妙，C h e n g d u6 1 0 0 3 1 ，C h n a ；2 C o m m e r cia lC o lle g e ，S w h u a nN o r m a l U n iv e r s it y ，c 啦6 1 0 0 6 8 ，C h n a ) A b s t r a ct ：N o ws ch e d u lin ginaa u t om a in t e n a n cew o r k s h o pisb ye x p e r ie n cea n dla cko fs cie n t if icp la n n in g I tr e s u lt salo n g e r t im et Ow a itf o rcu s t o m e r sa n dalo w e rca p a cit yu t iliz a t io n T os o lv et h isp r o b le m ，b a s e do nt h es ch e d u lin gt h e o r y ，t h isp a p e r s t u d ie do nt h ech a r a ct e r is t ica n da lg o r it h m A tf ir s t ，b u ilto p t im iz a t io ns ch e d u lin gm e t h o d so nt h eb a s iso fa n a ly s ist ot h es ch e d u lin go b j e ct iv e s ，m a ch in e ss u r r o u n d in g s ，w o r k in gch a r a ct e r is t ics ，a n dr e le v a n tco n s t r a in t s ，a n d8 0O n T h e nd e s ig n e dt h e s ch e d u lin ga lg o r it h mf o rt h isp r o b le m ，itb a s e do nd e co m p o s it io nm e t h o d sa n dco n s t r a in t - g u id e dh e u r is t ica lg o r it h m A tla s te x - a m p les h o w st h a tt h ea lg o r it h misf e a s ib le ，a n ds im u la t io nr e s u lt sd e m o n s t r a t et h ea lg o r it h mu s e dt oo p t im iz et h eo b j e ct iv ef u n c t io niss u p e r io r K e yw o r d s ：a u t om a in t e n a n cew o r k s h o p ；p la n n in ga n ds ch e d u lin g ；j o b b a s e dd e co m p o s it io nm e t h o d s ；co n s t r a in t g u id e dh e u - r is f ic a lg o r it h m 0引言 调度研究的问题是将稀缺资源分配给在一定时间内的不 同任务，它是一个决策过程，其目的是优化一个或多个目标。 对汽车维修车间作业排序的优化调度是针对实际问题构建模 型，运用相关的调度规则进行任务优化排序，这是调度理论在 服务组织内的应用。当前，在各个维修站中通常是依据先到先 服务规则( F C F S ) ，结合车间经理的经验进行工作任务的调度， 缺乏科学的规划，导致较长的客户等待时间，不利于企业提高 服务质量。 目前对于这一特定应用环境下的研究还比较缺乏，但是与 其相关的某些内容已有了大量的研究成果。汽车维修车间作 业排序是以最小化延迟时间和制造期为目标、受到达时间影响 的J o b s h o p 调度问题。在理论研究方面，包含三台设备以上的 J o b s h o p 调度问题已经被证明是强N P 难题，尚未找到精确解 法，研究集中于启发式算法上，如应用模拟退火算法、禁忌搜索 算法和遗传算法、蚁群算法等2 1 解决特定的J o b s h o p 问题。 此外，针对特定问题，研究者提出一些先进调度方法，如B a la s 等人”o 研究了加工车间调度问题的转换瓶颈启发式算法；M c C o r m ick 等人M 1 研究了多目标调度；E lk a m e l等人对分解算法进 行了研究”- s ；文献 9 1 2 研究了基于约束的采用人工智能 技术的调度系统。在解决现实问题时，这些理论规则和方法往 往被包含在一些更复杂的结构中。因为实际的调度问题都有 自己的特点，如不同实际问题的优化调度目标存在差异、机器 环境复杂程度各不相同等。 针对于此，本文对汽车4 s 维修车间的优化调度问题进行 研究，在以往理论研究的基础上，剖析这一实际应用问题的调 度目标、机器环境、加工特征和约束等细节，提出了优化调度模 型，设计调度算法，然后通过实例简要分析了模型及算法的可 行性。 1问题描述 汽车需要定期保养或出现故障需要维修，形成工作任务。 为满足客户的需要，4 s 店维修车间必须在有限资源条件下尽 快完成任务。维修车间的优化调度可以控制维修任务，实现维 修资源协调优化和高效运行。一个调度问题可以用三元组n 收稿日期：2 0 0 9 0 7 1 9 ；修回日期：2 0 0 9 - 1 1 1 7 基金项目：1 3 1 家自然科学基金资助项目( 7 0 6 7 2 0 1 3 ) ；铁道部件技开发计划重大资助项目 ( 2 0 0 8 2 0 1 9 ) 作者简介：扬琴( 1 9 7 8 ) ，女，四J 1 1 宜宾人，博士研究生，主要研究方向为生产作业、优化调度( y y m 渊 y a h o o 嗍伽) ；周国华( 1 9 6 6 ) ，男， 江苏张家港人，教授，博导。主要研究方向为生产管理 第5 期杨琴，等：汽车维修车间作业排序的优化模型及调度算法 1 6 8 7 卢以来描述。其中，a 域描述机器环境；卢域提供加工特征和约 束的细节；y 域描述最小化目标。以下从这三个方面对调度问 题进行描述。 1 ) 机器环境( d 域) 车间设备主要分为三个类别：机电设备( 包括举升机、制 动检测线、四轮定位仪、轮胎平衡机、轮胎拆装机等) 、钣金设 备( 包括车架校正仪、铝合金修复设备、点焊机、高效钣金整形 设备等) 和油漆设备( 包括喷漆房、研磨设备等) 。根据任务不 同，经过预先设定的工艺路线实现维修服务，本研究只针对某 一个班组接受的工作任务进行排序研究。- 2 ) 加工特征和约束( 口域) 汽车4 S 店维修车间加工具有以下特征和约束： a ) 优先性。维修保养时，工作任务具有优先级别，这是由 工作任务本身的紧急程度和客户的重要程度决定的。例如，针 对大客户构建快速通道，保养车辆通常比事故车辆有更严格的 出厂时间要求。 b ) 时效性。汽车的维修保养都必须在有限的时间内完 成，因此需要考虑完成工作任务的时限，即预计出厂时间，它是 指只要在此时间之前完成工作任务，不会造成延迟损失。 c) 动态性。维修保养环境是不断变化的，在此过程中会 遇到各种各样的随机干扰，如工作任务源源不断地到来、机器 故障、备件缺乏、维修时间的改变等。 3 ) 调度目标( 7 域) 服务型企业直接与客户接触，如何提供使客户满意的服务 是企业经营的关键。 加工任务不同会影响调度目标。汽车维修和保养过程中 涉及钣金油漆和复杂的机电维修，工作任务耗时较长，需要客 户将车辆交由车间代管修理，并在约定的时间取车。为了方便 客户，一般取件时间为下班或休息时间( 如1 2 ：0 0 或1 7 ：0 0 后) 。此类工作的制造期相对宽松，且允许出现为时不长的滞 后时间。这可以通过加班等方式来弥补，但会产生更多的费 用，带来滞后惩罚。优化调度的目标是滞后时间最小。 另外一类车辆仅仅需要简单的机电维修检测，耗时较短 ( 通常在6 0 9 0I I lin ) 。通常客户选择的是现场等待，一般等 待时间在1 2 0r a in 以内。同时，由于客户间存在的各种差异 ( 如大客户与普通客户) ，使得不同工作任务的优先级存在不 同。此类工作的制造期相对较紧，且不允许出现滞后，滞后会 带来客户的不满。优化调度的目标是在确保不滞后的基础上 实现加权完成时间最短。 2 优化调度模型设计 本文仅考虑特定条件下( 即给定出现故障或需要保养的 汽车数量、汽车入厂时间、维修的设备路线及每台设备上的维 修时间等) 维修车间的优化调度，在此基础上确定优化调度 方案。 2 1 符号与基本假设 下标i表示一台机器，下标，表示一项工作；如果一项工作 需要许多加工步骤或操作，则数对( i，歹) 指的是工作，在机器i 上的加工步骤或操作。 参数P # 表示工作，在机器i上的加工时间；，：f 表示工作，的 提交时间；d ，表示工作，的承诺完成时间；甜j 表示工作的权重， 由工作的紧迫程度、客户的重要性等因素决定；C ，表示工作J 离开系统的时间；r 表示工作J 的延迟时间。 变量表示操作( i，_ ) 的起始时间。 集合表示所有操作( f ，) 的集合；A 为所有线路约束( i， ) 一( k ，) 的集合，它需要工作在机器k 加工前先在机器i上 加工。 2 2 模型表达 r a in 乃( o p t ) m in 局 ( 1 ) s t 乃= 咖x ( 嘭一C j ，o ) ( 2 ) q 一 舶，( i，J ) E N ( 3 ) 5 I ， 0 ，( i，) E N ( 4 ) - - X # 珊，( i，) 一( t ，) A ( 5 ) 5 i X p d 或。4 5 # p # ，( i，J ) 和( i，Z ) ；i= 1 ，2 ， ，t n ( 6 ) O ，( j ，J ) e N ( 7 ) 模型中，式( 1 ) 为目标函数，体现了调度的目标是在优先 确保总滞后时间最小的基础上，尽量缩短加权完成时间。式 ( 2 ) 一( 7 ) 为约束条件。其中，式( 2 ) 度量了工作，的延迟时 间；式( 3 ) 保证工作_ 在离开系统之前完成了所有工序；式( 4 ) 确保工作歹的第一项操作是在工作，提交之后开始的；式( 5 ) 为工作约束，保证操作( k ，J ) 不能在操作( i，) 完成之前开始， 确保工作，在不同机器上的加工顺序；式( 6 ) 为机器约束，保证 了需要在同一台机器上完成的不同工作任务加工之间存在某 种排序；式( 7 ) 保证每道加工工序的时间大于0 。 3 调度算法 本文针对问题模型( 图1 ) ，采用分解法与约束引导的启发 式算法相结合的调度算法。在现实中，调度问题常常通过看上 去不那么准确的启发式算法来解决，原因是现实问题中往往存 在大量的随机事件，这些事件往往导致在执行原有调度时被迫 作出调整。 图1 调度结构图 3 1 分解法 3 1 1 分解法介绍 常用的分解法有基于机器的分解法、基于工作的分解法、 基于时间的分解法和混合方法，本文采用基于工作的分解法的 改进方法。 基于工作的分解法中，子问题具有不同的优先级，一次调 度一个工作。一个给定子问题的解是将一项工作的所有操作 插入一个部分调度中，这样使新的调度是可行的，且由于新工 作的插人造成优化目标( 制造期、滞后时间) 的增量最小。如 果一项新工作的插入是不可行的，那么在插入以前必须重新 调整。 1 6 8 8 计算机应用研究第2 7 卷 3 1 2 问题分解 通过问题描述可以看出，由于调度目标不同，工作任务具 有不同的优先级。据此将问题分解成多个子问题，子问题l涉 及的是由大客户提交的现场等待任务，设置最高的优先级，优 先排序；子问题2 涉及的是普通用户的现场等待任务，该任务 要求在尽量不滞后的基础上还要缩短服务等待时间期，因此优 先级次之，在子问题1 调度的基础上插入；子问题3 涉及的是 预约任务，此类任务的制造期较为宽松，并且可以一定程度地 接受滞后，所以最后安排，可以在子问题1 、2 调度的基础上插 入子问题3 的调度。 3 2 约束引导的启发式算法 问题分解后，运用约束引导的启发式算法对子问题1 、2 进 行作业调度。 3 2 1 算法 约束引导的启发式搜索源于人工智能领域，它是试图找到 一个可以满足各种约束条件的可行解，而非最优解。针对本案 例的情况，其算法步骤可以归结设置如下： a ) 设定承诺完成时间西。 b ) 对每项操作计算最早可能开始时间和最晚可能完成 时间。 c) 比较每台机器上的时间窗口。每台机器上的时间窗口 为r 。 喇。如果给定机器上的两个操作的时间窗口不重叠，那 么这两个操作间的优先关系可以确定，直接到d ) ；如果两个时 间窗口重叠，则要计算每个无序操作对的时间间隔。同一机器 f 上操作( f ，h ) 和( i，J ) 之间的时间间隔，盯( ) 州，) = 屯一 一p 访一p 诗，可能出现以下四种情况： ( a ) 若盯( 1 ， ) 叫f I ) O 且盯( i，) _ + ( ) 0 ，则要应用优先约束 条件( i， ) 一( i，蠡) ； ( b ) 若矿( j ， ) _ + ( f 。I ) O 且仃( i，k ) _ ( ih ) o ，则要应用优先约束 条件( i，露) 一( i， ) ； ( c) 若盯( 1 ) _ + ( m ) 0 且叮( i，k ) _ ( i，h ) 盯( ) - ( ， ) ，则应用优先 约束条件( ，五) 一( i，l| ) 。 e ) 返回a ) ，回溯放宽客户等待时间d ，。 f ) 加入一个新的优先约束，返回b ) ，更新时间，直至调度 结束。 3 2 2 问题求解 1 ) 对大客户的工作任务进行排序 对大客户的承诺完成时间存在一个上界d 。= 0 + 1 2 0 和一 个下界d l= + 却F ，初始值设定为弓= ( 屯+ d t ) 2 ，应用上述 算法求解。如果没有可行解，则重新设置承诺完成时间上界 d 。= r + 1 2 0 ，下界d 。为上次的d ，如此循环直至找到可行解。 2 ) 在问题1 排序的基础上插入问题2 普通客户发出的工作任务，的承诺完成时间4 = r + 1 2 0 ， 如果没有可行解，可与客户商量适当放宽承诺完成时间，或转 为预约取件任务，归类到问题3 。 4 案例 现截取某汽车维修车间上午8 ：3 0 ，1 0 ：0 0 的数据，如表 l所示，并应用上述方法进行调度分析。对约定时间取车的工 作任务，= O ，通过第4 组约束保证工作能按时完成；现场等待 取车的非重要客户的工作任务峨= 1 ；现场等待取车的重要客 户的工作任务山，= 5 。 。 表1某汽车维修站工作任务问题实例 任务叶0 专 机器顺序 加T 时间 1004 0 0 1 ，3 ，5 。6p lI = 2 6 ，丹J - 3 0 ，p 5 1 = 5 0 ，P 6 1 = 1 0 0 201 04 5 0 1 ，4 。3 ，5 ，6P 1 2 = 3 4 ，P 4 2 = 3 5 ，P 3 2 = 3 0 。P 5 2 = 6 0 ，P 6 2 = 1 1 0 3 14 0l 2 ，4 ，3p 2 3 = 1 5 ，P 4 3 = 3 0 ，P 3 3 = 2 2 4 55 51 5 8 2 。3 ，4p M = 2 0 ，P 3 4 = 3 6 ，p “= 2 9 5 16 0l胁 1 ，4p 1 5 = 7 0 ，p 4 5 = 4 0 657 0l鹋 1 ，3p 1 6 = 4 0 ，p 3 6 = 3 5 712 0 0 2 。3 。4p 2 7 = 2 0 ，P 3 7 = 3 5 ，P 4 7 = 3 0 4 1 问题分解 根据工作任务的紧急程度和时间限制，本例可分解成三个 子问题：问题1 ，V I P 客户的现场等待任务，包括任务4 和6 ；问 题2 ，普通客户的现场等待任务，包括任务3 、5 和7 ；问题3 ，预 约取件任务，包括任务1 和2 。 4 2 子问题求解 对各子问题采用约束引导的启发式算法求解。以问题1 为例： a ) 根据调度模型绘制不包括析取弧的析取图，如图2 所 示。 图2 子同题l无析取弧的析取图 b ) 依据已有条件计算所有操作的局部提交时间和工期， 如表2 所示。 表2 操作的局部提交时间和工期 堡堡堑生 2 4 5 5 9 3 3 47 51 2 9 4 ，4 1 1 1 1 5 8 I ，67 01 3 3 3 61 1 01 6 8 c) 计算同一机器上不同操作的时问间隔。 矿( 3 ，4 ) + ( 3 ，6 ) = 南6 一，一p 3 6 一p 3 4 = 1 6 8 7 5 - 3 5 3 6 = 2 2 盯( 3 6 ) + ( 3 ，4 ) = d 辩一r k p 3 6 一J P 籼= 1 2 9 1 1 0 3 5 3 6 0 且口( 3 6 ) _ + ( ，4 ) 0 ，则要应用优先约束 条件( 3 ，4 ) 一( 3 ，6 ) 。同理可以计算得到其他子问题的调度 结果。 4 3 解的整合 将子问题2 的解插入子问题1 。插入中如果工作对的时 第5 期 杨琴，等：汽车维修车间作业排序的优化模型及调度算法 1 6 8 9 间间隔o - 出现情况( c) 或( d ) ，优先保障子问题l的工作时间； 同时可与客户商量适当放宽子问题2 的承诺完成时间；同理， 插入子问题3 的调度结果。综合三个子问题，得到案例的最终 调度如图3 所示。 5 01 0 01 5 02 0 02 5 03 0 0 3 5 0 4 0 0 图3 案例最终调度 从甘特图得出目标函数值为乃= 9 0 ，哟c：f = 21 4 3 。相 对于当前企业中常用的F C F S 规则计算出的目标函数值Z = 1 0 7 ，z , o iq = 25 2 0 ，本文提出的调度算法优化了目标函数值。 以上程序均用C + + 编写，在奔腾双核、主频1 7 3G H z 的计算 机上进行实验仿真，C P U 运算时间小于0 0 5m g 。 5 结束语 汽车维修车间的优化调度是J o b s h o p 调度理论在企业的 实际应用。本文针对当前企业中主要采取F c巧规则进行调 度，导致较长的客户等待时间和较低的设备利用率等问题，在 优化调度理论的基础上，对这一调度问题和算法进行了研究， 分析了这一实际问题的特征，建立了相应的优化调度模型，设 计了分解法与约束引导的启发式算法相结合的调度算法。最 后以实例分析验证了算法的可行性，通过对比仿真结果展示了 本文所用算法相对于F C F S 规则在优化目标函数值上的优越 性。 参考文献： I 】L ccr rG ，B I I L A U TJC At a b us e a r cha n dag e n e t ica lg o r it h mf o r s o lv in gab icr it e r iag e n e r a lj o b8 h o ps ch e d u lin gp m b lcm J E u r o p e a n J o u m a lo fO p e r a t io n a lR e s e a r ch 。2 0 0 8 ，1 9 0 ( 2 ) ：3 9 8 4 1 1 ( 上接第1 6 8 5 页) 问题。由于B 细胞算法没有使用a g if I g 算子， 使用了超变异算子的一种变化 连续区域超体变异算子 ( C R H O ) 。显然C R H O 满足条件1 ，因而可获褥B C A 收敛性的 证明。 参考文献： 1 B U R N E TFM T h ecle u a l s e le ct io nt h e o r yo fa cq u ir e dim m u n it y M C a m b r id g e ：C a m b r id g eU n iv e r s it yP r e e a ，1 9 5 9 2 】D eC A S T R OLN ，V o nZ U B E NFJ L e a r n in ga n do p t im iz a t io nu s in g t h eclo n a lle e d o np r in cip le J I E E ET r a n so nE v o lu t io n a r y C o m p u t a t io n ，2 0 0 2 ，6 ( 3 ) ：2 3 9 2 5 1 3 】V I L L A L O B O S A R I A SM ，C O E L L O C O E L L OCA ，H E R N A N D E Z - L E R M A0 C o n v e r g e n cea n a ly s iso fam u lt i- o b j e ct iv ea r t if icia lim m u n e s y s t e m 目6 , , o r it h m C 】P r o co fL e ct u r eN o t e sinC o m p u t e rS cie n ce B e r lin ：S p r in g e r ，2 0 0 4 ：2 2 6 2 3 5 4 C L A R K EE 。H O N EA ，T I M M I SJ AM a r k o vch a inm e d a lo f t h eB - ce ll 出o n t h m fC e r o eo ft h e 4 t hI n t e r n a t io n a lC o n f e r e n ceo nA a if icia l h n m u n eS y s t e m s B e r lin ：S p r in g e r ，2 0 0 5 ：3 1 8 3 3 0 【5 R U D O L P HG F in it eM a r k o vcb a inr e s u lt sine v o lu t io n a r ye o m p u t a - t ie n ：at o u rd h o r iz o n J F u n d a m e n t aI n f o r m a t ice e ，1 9 9 8 。3 5 ( 1 - 2 G A OJ ie ，S U NL in y a n ，G E N BM Ah y b r idg e n e t ica n dv a r ia b le n e ig h b o r h o o dd e s ce n ta lg o r it h mf o rf le x ib lej o bs h o ps ch e d u lin gp r o b ie m s J C o m p u t e r s & O p e r a t io n sR e s e a r ch ，2 0 0 8 ，3 5 ( 9 ) ：2 8 9 2 2 9 0 7 【3 B A L A SE ，L E N S T R AJK ，V A Z A C O P O U L O SA T h eo n e m a ch in e p r o b le mw it hd e la y e dp r e ce d e n ceco n s t r a in t sa n dit su s einj o bs h o p s ch e d u lin g J M a n a g e m e n tS cie n ce 。1 9 9 5 ，4 1 ( 1 ) ：9 4 1 0 9 【4 】M cC O R M I C KST ，P I N E D OMLS ch e d u lin gnin d e p e n d e n tj o bo nu - n if o n nm a ch in e sw it hb o t hf lo wt im ea n dm a k e s p a no b j e ct iv e s ：ap a r a - m e t r ica n a ly s is J J o u m a lo fC o m p u t in g ，1 9 9 5 ( 7 ) ：6 3 - 7 7 5 E L K A M E LA ，M O H I N D R AA Ar o ilin gh o r iz o nh e u r is t ic f o rr 删iv c s ch e d u lin go fb a t chp r o ce s so p e r a t io n J E n g in e e d n gO p t im iz a - t io n ，1 9 9 9 ，3 1 ( 6 ) ：7 6 3 7 9 2 6 L I UM in ，H A OJ in g - h u a ，W UC h e n g Ap r e d ict io nb a s e dit e r a t iv ed e - e n m p o s it ie na lg o r it h mf o r s ch e d u lin gla r g e s ca lej o bs h o p s J M a t h e m a t ica la n dC o m p u t e rM o d e lin g ，2 0 0 8 ，4 7 ( 3 - 4 ) ：4 1 1 - 4 2 1 ， 7 】K E L L YJD ，Z Y N G I E RD H ie r a r ch ica ld e co m p o s it io nh e u r is t ic f o r s ch e d u lin g ：co o r d in a t e dr e a s o n in gf o rd e ce n t r a liz e da n dd is t r ib u t e dd e - e is io n m a k in gp r o b le m s J C o m p u t e r sa n dC h e m ica lE n g in e e - 岫，2 0 0 8 ，3 2 ( 1 1 ) ：2 6 8 4 2 7 0 5 g S Z W A R CW D e e n m p o s it io nins in g lem a ch in es ch e d u lin g J A r 卜 n a t so fO p e r a t io n sR e s e a m h ，1 9 9 8 ，8 3 ( 1 ) ：2 7 1 2 8 7 【9 】C H E N GCC ，S M I T HSF A p p ly in gco n s t r a in ts a t is f a ct io nt e ch n iq u e s t oj o bs h o ps ch e d u lin g J A n n a lso fO p e r a t io n sR e s e a r ch 。1 9 9 7 7 0 ( I ) ：3 2 7 - 3 5 7 1 0 】N U U T E NW PM 。A A R T SEHL Aco m p u t a t io n a l s t u d yo fco n s t r a in t s a t is f a ct io nm u lt ip leca p a cit a t e dj o bs h o ps ch e d u lin g J E u r o p e a n J o u r n a lo fO p e r a t io n a lR e s e a r ch ，1 9 9 6 ，9 0 ( 2 ) ：2 6 9 2 8 4 1 1 G A R R I D OA ，O N A N D I AE ，S A P E N A0 P la n n in ga n ds ch e d u lin gin 8 1 1e - le a r n in ge n v ir o n m e n t ：aco n s t r a in t p r n g r a m m in g - b n s e da p p r o a ch J E n g in e e n n gA p p lica t io n so fA r t if icia lI n t e llig e n ce 。2 0 0 8 。2 1 ( 5 ) ：7 3 3 7 4 3 1 2 S A L I D OMA 。G A R R I D OA 。B A R T A KR I n t r o d u ct io n ：s p e cia lis s u e o nco n s t r a in ts a t is f a ct io nt e ch n iq u e sf o rp la n n in ga n ds ch e d u lin gp r o b - I ct u s J E n g in e e r in gA p p lica t io n so fA r t if icia lI n t e llig e n ce ，2 0 0 8 ， 2 1 ( 5 ) ：6 7 9 6 8 2 4 1 ：6 7 - 8 9 【6 】H A M M E RPL ，R U D E A N US B o o le