二机連续性零工工厂总时程最小化排程问题之研究

朝阳科技大学工业工程与管系硕士文二机续性工工厂总时程最小化排程问题之研究TWOMACHINENOWAITJOBSHOPSCHEDULINGPROBLEM指导教授廖研究生詹经芳博士咏翔中华民国九十三七月二十七日朝阳科技大学工业工程与管系DEPARTMENTOFINDUSTRIALENGINEERINGANDMANAGEMENTCHAOYANGUNIVERSITYOFTECHNOLOGY硕士文THESISFORTHEDEGREEOFMASTER二机续性工工厂总时程最小化排程问题之研究TWOMACHINENOWAITJOBSHOPSCHEDULINGPROBLEM指导教授廖经芳CHINGFANGLIAW研究生詹咏翔YUNGHSIANGCHAN中华民国九十三七月二十七日27,JULY,2004中文摘要工工厂JOBSHOP之排程问题可简单地描述如下，N项独工件及M部同的机器，每项工件必须依其作业顺序限制进入机器进处，同一时间内，每部机器最多只能针对一项工件进处且每项工件仅能在一部机器上加工。工工厂之排程问题常于各弹性制造系统。所谓续性NOWAIT是指工件进入生产系统中，一旦开始加工就必须持续地进，直到完工，允许工件有闲置或等待的况发生。具有续性限制之排程问题常于许多产业，如，在属熔融业中，已加热之属为防止产生缺陷，在却之前必须持续地在高温时进一的作业。同样地，在塑料成型及银制品产业，其一作业必须接即地进，以防止温下。本研究针对二机工工厂受续性加工之限制，以总时程MAKESPAN最小化为研究目标，发展一启发式算法HEURISTIC与分枝界限算法BRANCHANDBOUND。启发式算法能迅速且有效地解决大规模之问题，且启发式算法之结果亦可应用于分枝界限算法之上限值。本研究亦将设计分枝界限算法之分枝策、下限值和淘汰法则，以期能有效地求取最佳解。最后，本研究将以大随机产生之测试问题，评估所发展之启发式演算法与分枝界限算法之求解绩效。关键词工工厂、续性、总时程、分枝界限算法IABSTRACTTHEJOBSHOPSCHEDULINGPROBLEMCANBESTATEDASFOLLOWSTHEREARENINDEPENDENTJOBSANDMDIFFERENTMACHINESTHEREISRESTRICTIONONTHEORDERINWHICHTHEOPERATIONSOFAJOBARETOBEPERFORMEDEACHMACHINECANPROCESSATMOSTONEJOBATATIMEANDEACHJOBCANBEPROCESSEDONONEMACHINEATATIMEJOBSHOPSCHEDULINGAREOFTENENCOUNTEREDINFLEXIBLEMANUFACTURINGSYSTEMSSCHEDULINGPROBLEMSWITHNOWAITCONSTRAINTSOCCURINMANYINDUSTRIESFORINSTANCE,INHOTMETALROLLINGINDUSTRIES,WHERETHEHEATEDMETALHASTOUNDERGOASERIESOFOPERATIONSATCONTINUOUSLYHIGHTEMPERATURESBEFOREITISCOOLEDINORDERTOPREVENTDEFECTSSIMILARLY,INTHEPLASTICMOLDINGANDSILVERWAREPRODUCTIONINDUSTRIES,ASERIESOFOPERATIONSMUSTBEPERFORMEDTOIMMEDIATELYFOLLOWONEANOTHERTOPREVENTDEGRADATIONWECONSIDERTHEPROBLEMOFMINIMIZINGMAKESPANINATWOMACHINENOWAITJOBSHOPENVIRONMENTINOURRESEARCH,WEPRESENTAHEURISTICSOLUTIONMETHODFORSOLVINGLARGESCALEDPROBLEMSWEALSODEVELOPABRANCHANDBOUNDALGORITHMWEUSEANUPPERBOUNDBASEDONTHEHEURISTICALGORITHMDEVELOPED,ANDPROPOSESOMEDOMINANCERULESTOHELPPRUNINGUNPROMISINGNODESINTHEBRANCHANDBOUNDSEARCHTREEFINALLY,COMPUTATIONALEXPERIMENTSARECONDUCTEDTOEVALUATETHEPERFORMANCESOFTHEPROPOSEDALGORITHMSKEYWORDJOBSHOP、NOWAIT、MAKESPAN、BRANCHANDBOUNDII致谢本文能够顺地完成，首先必须感谢我的指导教授廖经芳师，在这的研究过程中细心地指导，才使得本文得以顺地完成。同时也要感谢大同资经系高有成师与朝阳工管系郑纯媛师，位师于文口试期间，针对本研究的各项缺失，提出详尽地建议，使得本文在结构及内容上趋于完善。另外也要感谢朝阳工管系陈铭芷师与王敏师平时的指教与建议。再要感谢学群的同学竹青、南蒨、进、权颖及所有班上同学的鼓与帮助，还有柏秀学姊和建韶学弟的陪伴与支持，谢谢你们的照顾与关怀，使得我这的研究生涯过得加充实与多采多姿。最后要感谢我最爱的家人，因为有你们的支持，让我在求学的阶段，能够毫无后顾之忧的完成学业，你们的支持与鼓一直是我最大的动源，这此致上我最深的谢意，并且将这份成果献给你们。詹咏翔谨志于朝阳科技大学工业工程与管系研究所中华民国九十三七月III目中文摘要IABSTRACTII致目表图谢IIIIV目VII目VIII第一章绪111研究背景与动机1111112113排程问题的分1排程问题的评估准则2排程问题的求解方法312研究问题描述与限制413研究架构5第二章文献探讨721程工厂之文献探讨7211212213214续性限制8考虑整备时间8有限暂存区9具平机器特性之程工厂922工工厂之文献探讨10221续性限制10222单位加工时间1123开放工厂之文献探讨11IV231续性加工的复杂分析12232考虑搬运时间1224文献汇整12第三章研究方法1631符号定义1632学模式1833启发式算法19331启发式算法之设计19332启发式算法之实明2534分枝界限算法29341342343344分枝策29上限值42下限值42淘汰法则45第四章实验证5041分枝界限算法之绩效评估51411上限值及下限值之绩效评估51412分枝界限算法之求解绩效5342具有瓶颈机台之绩效评估5643同比加工顺序之绩效评估58第五章结与建议6051结60V52未研究方向62考文献63VI表目表21表22表23表31表32表33表34表35表36表37表38表41表42表43表44表45表46表47表48程工厂之文献整13工工厂之文献整14开放工厂之文献整15工件的加工时间25指派问题之成本表26结合工件对27未配对工件的加工时间27转换后之排对应27弧之分群28部分一与部分二结合28工件之加工时间44上限值与下限值之绩效评估PI,JU1,2552上限值与下限值之差距UBLB52分枝界限算法之求解时间秒53分枝界限法节点与时间之关系PI,JU1,2554分枝界限算法之平均节点55启发式算法之绩效考虑瓶颈机器56有无瓶颈机器之求解时间57同比加工顺序之绩效58VII图目图11图31图32图33图34图35图36图37图38图39研究程图6工件对I,K之示意图17CASEA区块B优先于工件对I,K20CASEB工件对I,K优先于区块B21GGSCHEME的成本计算方式PINEDO199522有向图128有向图228启发式算法最佳之排程29分枝界限算法之分枝策30I1,K2之示意图31图310图311图312图313图314图315图316图317图318图319图320图321图322SK之三种型33部分排程SK之分34SK属于TYPE1且FMK1M135SK属于TYPE1且FMK1M236SK属于TYPE1且FMK1M136SK属于TYPE1且FMK1M237SK属于TYPE2且FMK1M138SK属于TYPE2且FMK1M238SK属于TYPE2且FMK1M139SK属于TYPE2且FMK1M240SK属于TYPE3且FMK1M140SK属于TYPE3且FMK1M241SK属于TYPE3且FMK1M141VIII图323图324图325图326SK属于TYPE3且FMK1M242下限值的结果45法则11排程S与S之比较46法则21排程S与S之比较48IX第一章绪11研究背景与动机排程SCHEDULING之定义为在产能受限的生产系统中，如何安排作业的程序，使得预期的目标达到最佳化。日常生活中到处可以到排程的应用，如学校师之授课内容和教室的安排、医护人员的班，和机场班机的起等。在生产系统中，因为系统的资源有限，为充分地运用资源，并且满足机器或物的加工特性，所以排程的规划必须因应现场况而进同的设计，使得工作完成的同时，亦能获得最大的润。因此，排程为生产系统中重要的一环。机器的加工型相当地多，其中，续性NOWAIT是指工件进入生产系统中，一旦开始加工就必须持续地进，直到完工，允许工件有闲置或等待的况发生，此种型的加工主要是因为生产技术之限制，或物之特性如温、黏等，使得作业程序必须持续地进，常的子如属熔融业，因为属在常温时呈现固态，所以加工的过程必须持续地在高温中处。此种特性亦常于塑料、电镀和化学加工过程等等。111排程问题的分排程问题依照工件处的性质进分，可以区分为单程处SINGLEOPERATION及多程处MULTIPLEOPERATIONS的排程问题。单程处是指工件只需要经过一部机器进处，多程处是指工件必须经过部机器的处，工件的加工程序才可以完成。单程处的排程问题依加工机器之又可分如下1单机排程SINGLEMACHINESCHEDULING只有一部机器，每个工件必须在此部机器进处。12平机排程PARALLELMACHINESCHEDULING有部拥有相同作业能的机器，工件可任意选择其中一部机器以进加工，各部机器可以同时加工，而且受彼此的影响。多程处的排程问题依工件之加工特性可分如下1程工厂FLOWSHOP各个工件的处程序均相同，即工件经过各部机器的顺序是相同的；排程的重点是决定各部机器对工件的处顺序，此种加工型适用于相同或似产品之大生产。2工工厂JOBSHOP各个工件的处程序尽相同，而且必经过所有的机器；排程的重点是决定各部机器处工件的顺序，此种加工型较常于各弹性制造系统。3开放工厂OPENSHOP开放工厂之排程特性为各工件之处程序是可任意决定的，即必须同时考虑工件经过机器的顺序及机器对工件的加工程序。当工件必须依照特定的程序到各部机器进处时，即与工工厂相同；当工件的加工顺序均相同时，即与程工厂相同。在现实生活中，有许多属于开放工厂的排程问题，如汽修厂维修作业、质量检测或身体健康检查等等。112排程问题的评估准则当相同的排程问题考虑同的评估准则时，就会造成解题困难的明显差。如平机考虑程时间FLOWTIME最小化的问题是非常容2的，当排程问题之目标为总时程MAKESPAN时，其解题困难则明显地提升【60】。各种生产方式有个别的特性，以考的绩效目标而言，最常的排程评估准则包括1总完工时间TOTALCOMPLETIONTIME最小化2总时程最小化3总程时间TOTALFLOWTIME最小化4总延迟时间TOTALTARDINESS最小化及5延迟的工件NUMBEROFTARDYJOBS最少化等种。113排程问题的求解方法为求解排程问题，各种方法断地被提出，较常用求解排程问题的方法可区分为下三种，各种方法皆有优缺点，以下就各种方法作简单的描述。1派工法则DISPATCHINGRULE常的派工法则，包括最短处时间法则SHORTESTPROCESSTIME,SPT、最长处时间法则LONGESTPROCESSTIME,LPT、最早到期日EARLIESTDUEDATE,EDD、关键比法CRITICALRATIO,CR及最小浮时法MINIMUMSLACKTIME,MST等等。派工法则虽然容解，而且可以快速地解决问题，但是处大规模的问题时，其求解质量往往较想。2近似解法APPROXIMATIONMETHOD当问题规模扩大时，求解最佳解需要很长的时间，所以，实务上常以近似解取代最佳解，近似解之求法可分为启发式算法和搜寻法SEARCH种。启发式算法是针对问题特性进特殊的设计，一般而言启发式算法之求解绩效皆十分想。搜寻法中，以基因算法GENETICALGORITHM、模拟退火法SIMULATEDANNEALING及塔布搜寻法TABUSEARCH最为普遍，此方法之求解绩效亦相当地想，但因较难解与应用，故实务上之使用仍未十分普遍。33最佳解法OPTIMIZATIONMETHOD透过分枝界限算法BRANCHANDBOUND或动态规划DYNAMICPROGRAMMING等方法可求得最佳解。使用分枝界限法或动态规划做为求解的工具时，虽然可以得到最佳解，但是求解过程相当地繁杂又耗时，而且受限于计算机的资源，所以解题规模容受到限制，因此实务的应用并广泛。但是在评估启发式算法之求解质量时，通常必须与最佳解之结果进比较，所以最佳解法如分枝界限或动态规划依然有其存在的价值与必要。12研究问题描述与限制工工厂中工件的加工程序尽相同，此问题大属于NPHARD的问题，最佳解求得，所以许多学者致于研发有效的近似解法，因此，工工厂之求解域仍有相当大的发展空间。本研究所要探讨的是二机工工厂在续性的限制下总时程最小化的排程问题。我们定义问题为二部机器的工工厂，有N项独工件，每项工件必须进入其所需的机器进处，而且必须符合续加工的原则，并以总时程最小化为目标。本研究所探讨之二机工工厂之排程问题，其基本假设如下12机器可以随时作业，且考虑机器故障的问题。机器可以闲置，但作业开始加工后就必须完成该项作业才可以停止，即允许中断PREEMPTION之情况。考虑机器的整备时间。同一时间内，机器只能针对一项工件作处，且工件仅能在一部机器上加工。3445678工件彼此独。所有的工件在一开始就可以进加工。工件于各部机器的加工时间为已知的常。所有的作业为彼此独的作业，具任何优先级限制。13研究架构本研究之研究架构包括以下各部分，研究程如图11所示第一章首先针对排程问题作探讨，确定研究主题为二机工工厂在续性限制下总时程最小化之排程问题，针对研究主题提出问题描述与基本假设。第二章针对相关排程问题进文献之收集与解。第三章设计研究的方法。将研究方法分为近似解与最佳解部分，并且以实进明。第四章将设计的方法，以C语言撰写程序，并进求解绩效评估。第五章将本研究所得之结与心得作一汇整，提出建议及未研究方向。5图11研究程图6结与建议撰写程序与绩效评估发展分枝界限算法发展启发式算法相关文献探讨确定研究主题二机续性工工厂第二章文献探讨近有许多的研究与续性NOWAIT和阻断性BLOCKING有关，续性的特性是工件自开始加工到完成必须持续地进，可中断；阻断性的特性是机器间无工件暂存区的排程问题。自1970起，有许多关于此问题的求解方法与复杂分析被提出。GRAHAMETAL1979【11】将所有的排程问题以|的符号表示，其中为机器加工的型态，如程工厂F、工工厂J、开放工厂O；为工件的特殊限制，如暂存区的个B、续性NOWAIT；为绩效目标种，如周期时间CT、总时程CMAX。21程工厂之文献探讨1954JOHNSON【20】针对二机程工厂，以总时程最小化为目标，提出一个简单而复杂COMPLEXITY为ONLOGN的最佳解算法；GILMOREANDGOMORY1964【10】将JOHNSON所提的问题延伸至F2|NOWAIT|CMAX或CT，并且提出一最佳解法；HALLANDSRISKANDARAJAH1996【15】验证此多项式演算法的复杂为ONLOGN；ROCK【45】证明F2|NOWAIT|LMAX与F2|NOWAIT,RI|CMAX或CT是相等的问题，并提出一算法以求解F2|NOWAIT|CI；在该文章中亦证明机器大于三部时，问题的困难将大幅提升为NPCOMPLETE。KAMOUNANDSRISKANDARAJAH1993【21】证明此问题与F3|BLOCKING|CMAX或CT相等，HALLANDSRISKANDARAJAH1996【15】则针对续性NOWAIT和阻断性BLOCKING的加工特性，将的研究做汇整。7211续性限制ROCK1984【45】探讨F2|NOWAIT,PIJ1|CMAX或CT的问题，以GILMOREANDGOMORY所提的方法为基础，提出复杂为ONLOGN的算法。SRISKANDARAJAHANDLADET1986【47】提出一简单的启发式算法以求解F2|NOWAIT,PIJ0,1|CI问题。PIEHLER1960【38】证明FM|NOWAIT|CMAX的问题与TSPTRAVELINGSALESMANPROBLEM问题相等；LAWLERETAL1985【26】针对FM|NOWAIT|CMAX问题发展出以TSP为基础之求解方法，其复杂为ON2。VANDEMANANDBAKER1974【57】发展出相当接近最佳值之下限值，将此方法应用至分枝界限法，以求得FM|NOWAIT|CI的最佳解，并且以6部机器，12个工件为作明。LEVNER1969【31】发展分枝界限法求得FM|BLOCKING|CMAX问题的最佳解，GUPTA1976【14】和SZWARC1981【54】则研究FM|NOWAIT|WIII的问题，其中WI为工件I之权重，II为工件I在排程中的机器闲置时间。212考虑整备时间STRUSEVICH1990【50】针对F2|NOWAIT|CMAX问题，将工件的处时间分为整备SETUPTIME、加工PROCESSINGTIME和搬运时间REMOVALTIME三方面研究，其中，机器2的整备时间可以和机器1的加工时间重迭，证明此问题可以改变为TSP的特。LOGENDRANANDSRISKANDARAJAH1993【32】将此问题延伸至阻断性的问题，证明其为NPHARD；POTTSANDSRISKANDARAJAH2000【19】针对相同的问题提出近似解算法，并且证明CH/C4/3，MAXMAX其中CH为近似解法求得之总时程，C为最佳解的总时程。MAXMAX8213有限暂存区当暂存区个B为0时，可以用GILMOREANDGOMORY的方法作处；当BN，用JOHNSON1954【20】的方法可以求得最佳解。PAPADIMITRIOUANDKANELLAKIS1980【37】证明当0BN1，F2|B|CMAX的问题为NPCOMPLETE，并且针对B1的问题提出算法。首先用GILMOREANDGOMORY之方法找到F2|NOWAIT|CMAX的最佳解，再决定F2|B1|CMAX之排程顺序，此方法之最差求解绩效WORSTCASERATIO为CH/C3/2。DUTTAANDCUNNINGHAM1975MAXMAX【8】用动态规划研究此问题，而且证明此方法适用于B18之问题；并且用穷举法ENUMERATIONAPPROACH处工件为20之问题。LEISTEN1990【29】将此问题扩充至无限暂存区个的问题，针对此问题比较个启发式算法，指出NAWAZETAL1983【35】之算法为最佳。214具平机器特性之程工厂KURIYAN1987【25】针对相同的加工时间，而且相同作用的机器是相同MI的情况，以总时程最小化为目标，提出排序法LISTSCHEDULINGHEURISTIC，并且证明最差比值CH/C为21/。SRISKANDARAJAHMAXMAXANDSETHI1989【48】将排序法和GILMOREANDGOMORY之方法结合以求取F2|NOWAIT,M1M22|CMAX的问题，其中M1、M2为第一站、第二站平机的个，并证明CH/C31/。SRISKANDARAJAH【49】将LPT法则应MAXMAX用到穷举法，证明比值范围为7/32/3CH/C8/32/3，当问题具有MAXMAX阻断性的加工限制时，此比值范围仍然是有效的。922工工厂之文献探讨工工厂中工件的加工程序尽相同，此问题大属于NPHARD的问题，最佳解求得，所以许多学者致于研发有效的近似解法，如ADAMS,BALAS,ANDZAWACK1988【2】提出移动瓶颈法SHIFTINGBOTTLENECKPROCEDURE，TAILLARD1994【55】和NOWICKIANDSMUTNICKI1996【36】的塔布搜寻法，VANLAARHOVEN,AARTS,ANDLENSTRA1992【58】的模拟退火法，JAINANDMEERAN1998【18】的经网法NEURALNETWORKALGORITHM，DELLACROCE,TADEI,ANDVOLTA1994【7】和LEE,PIRAMUTHUANDTSAI1997【28】的基因算法，以及APPLEGATEANDCOOK1991【4】之分枝裁减法BRANCHANDCUTALGORITHM等。221续性限制SAHNIANDCHO1979【60】证明本研究所探讨问题J2|NOWAIT|CMAX之复杂为NPHARD；SRISKANDARAJAHANDLADET1986【47】证明J3|NOWAIT,PIJ1|CMAX和J3|NOWAIT,PIJ1|CI问题的复杂均为NPHARD；HALLANDSRISKANDARAJAH1996【15】将此问题受续性或阻断性限制的相关研究做汇整。续性工生产之排程问题是相当困难的，REDDIANDRAMAMOORTHY1973【43】针对JM|NOWAIT|CMAX问题，设计一有效的下限值。ADAMSETAL1988【2】针对工工厂无限制暂存区的情形下，发展一有效的解决方法，此方法对于NOWAIT和BLOCKING问题的解决亦很有帮助，KUBIAK1989【22】提出一动态规划算法，解决J2|NOWAIT,PIJ1|CMAX问题，其中工件于相同的机台可被加工次，其复杂为ON5K，其中K为工件的总处。10222单位加工时间JACKSON于1956将JOHNSON的算法作修改，以线性的时间算法求解二部机器的工工厂问题，GONZALEZANDSAHNI1976【12】验证J2|PIJ0,1,PMTN|CMAX问题为NPHARD，TIMKOVSKY1985【56】、KUBIAKETAL1995【24】和HEFETZANDADIRI1982【16】针对J2|PIJ1|CMAX问题提出伪多项式算法PSEUDOPOLYNOMIALALGORITHM，BRUCKER1982【5,6】将HEFETZANDADIRI1982的方法应用至J2|PIJ1|LMAX的问题。KRAVCHENKO2000【53】6针对J2|PIJ1|UI之问题提出复杂为ON之求解方法，研究中亦证明J2|PIJ1|WIUI为NPHARD，并且提出一伪多项式算法，证明其复杂为ON5WI。LAWLERETAL1993【27】证明下的问题属于NPHARDJ2|PIJ0,1|UI、J2|PIJ1,2|UI和J3|PIJ1|UI，LENSTRAANDRINNOOYKAN1979【30】指出J2|PIJ1,2|CMAX和J3|PIJ1|CMAX均为NPHARD的问题。23开放工厂之文献探讨HALLANDSRISKANDARAJAH1996【15】在文章中提到，程工厂和开放工厂中，机器为2，加工的限制条件为续性或阻断性时，此问题皆相等；GAREYANDJOHNSON1979【9】指出当机器大于2时，开放工厂和工工厂问题的求解就变得相当地困难。GONZALEZANDSAHNI1976【12】研究O2|CMAX之问题，提出一个ON最佳解算法，并且证明O3|CMAX的问题为NPHARD；ACHUGBUEANDCHIN1982【1】证明O2|CI为NPHARD。PINEDO1995【40】针对O2|CMAX的问题，在书中提出LAPTLONGESTALTERNATEPROCESSTIMEFAST派工法则求取最佳解；PINEDOANDSCHRAGE1982【39】将开放工厂的相关研究做汇整。11231续性加工的复杂分析GONZALEZANDSAHNI1976【12】针对O2|CMAX提出解法，此复杂为ON，亦证明O3|CMAX属于NPHARD，并于1979将研究扩充至工件受续性加工之限制，证明O2|NOWAIT|CMAX属于NPHARD；ACHUGBUEANDCHIN1982【1】证明O2|NOWAIT|CI属于NPHARD。KUBIAKETAL1991【23】证明O2|NOWAIT|CMAX和O3|NOWAIT|CMAX之问题皆属于NPHARD；KAMMOUNANDSRISKANDARAJAH1993【21】发现O2|NOWAIT|CMAX与O2|BLOCKING|CI问题的相等性，亦证明该问题属于NPHARD。GONZALEZ1982【13】证明O|PIJ0,1,NOWAIT|CMAX或CI为NPHARD，ADIRIANDAMIT1984【3】提出复杂为ONM的最佳解算法，以求解O|PIJ1,NOWAIT|CI或CMAX的问题。232考虑搬运时间二机开放工厂考虑搬运时间的况，以O2|I|CMAX表示，AMICO1995【33】和RAYWARDSMITH1992【42】分别针对此问题与搬运时间皆相等的问题，证明这些问题皆属于NPHARD，STRUSEVICH1998【51】针对此问题提出一算法，所得的解与最佳解的比值为8/5，于1999又提出复杂为ONLOGN的方法，并且与最佳解做比较，其比值为3/2。24文献汇整程工厂、工工厂和开放工厂的文献相当地多，在此无法一一讨，因此仅以下表做汇整，概述各学者的研究成果。12表21程工厂之文献整注PAPOLYNOMIALTIMEALGORITHMEXISTSPPAPSEUDOPOLYNOMIALTIMEALGORITHMEXISTSNPNPHARD13问题复杂作者研究内容F2|NOWAIT|PGILMOREANDGOMORY1964CMAX,CI复杂ONLOGN与F2|BLOCKING|相似F2|NOWAIT|LMAXNPROCK1984B与F2|NOWAIT,RI|,CMAX,CT相等F2|NOWAIT|CINPROCK1984B复杂为ONLOGNF3|NOWAIT|CMAXNPROCK1984A与F3|NOWAIT|CT相似，复杂ON2F2|NOWAIT,PIJ1|CMAXPROCK1984F2|NOWAIT,M11,M22|CMAXNPSRISKANDARAJAHANDLADET1986与M12,M21的问题相同，当条件改为BLOCKING亦相同F2|BLOCKING,M11,M22|CTNPKAMOUNANDSRISKANDARAJAH1993与M12,M21的问题相同，当条件改为NOWAIT亦相同F2|BLOCKING,SEPARATED|CMAXNPLOGENDRANANDSRISKANDARAJAH1993F3|BLOCKING|CMAXNPPAPADIMITRIOUANDKANELLAKIS1980探讨复杂，与F3|BLOCKING|CT相等KAMOUNANDSRISKANDARAJAH,1993表22工工厂之文献整1993复杂为ONKSAHNI1976I注PAPOLYNOMIALTIMEALGORITHMEXISTSPPAPSEUDOPOLYNOMIALTIMEALGORITHMEXISTSNPNPHARD14问题复杂作者研究内容J2|PIJ1|CMAXPPTIMKOVSKY1985、KUBIAKETAL1995和HEFETZANDADIRI1982提出伪多项式算法J2|NOWAIT|CMAXNPSAHNIANDCHO1979与J2|BLOCKING|CT问题相等KAMOUNANDSRISKANDARAJAH,J2|NOWAIT,PIJ1|CMAXPPSRISKANDARAJAHANDLADET1986KUBIAK1989复杂为ON5K，K为工件的作业总J3|NOWAIT,PIJ1|NPSRISKANDARAJAHANDLADET1986为CI或CMAXJ2|NOWAIT,PIJ1|CMAXPADAMSETAL19885J2|PIJ0,1,PMTN|CMAXNPGONZALEZANDJ2|PIJ0,11,2|J3|PIJ1|PLAWLERETAL1989为UJM|NOWAIT|CMAXNPREDDIANDRAMAMOORTHY1973设计一下限值表23开放工厂之文献整注PAPOLYNOMIALTIMEALGORITHMEXISTSPPAPSEUDOPOLYNOMIALTIMEALGORITHMEXISTSNPNPHARD15问题复杂作者研究内容O2|CMAXO3|CMAXPGONZALEZANDSAHNI1976复杂为ONO2|CMAXPPINEDO1995提出LAPT派工法则O2|CINPACHUGBUEANDCHIN1982O|PIJ1|PADIRIANDAMIT1984为CI或CMAX；复杂为ONMO|PIJ1|PLIUANDBULFIN1988为TI或UI；复杂为ON2MO2|NOWAIT|CMAXNPSAHNIANDCHO1979与O2|BLOCKING|CT问题相等KAMOUNANDSRISKANDARAJAH1993O2|NOWAIT|CINPACHUGBUEANDCHIN1982探讨复杂O|NOWAIT,PIJ0,1|NPGONZALEZ1982为CMAX或CIO|NOWAIT,PIJ1|PADIRIANDAMIT1984为CI或WIUI；复杂为ONMO|NOWAIT,PMTN|CMAXNPSTRUSEVICH1991第三章研究方法分枝界限算法是排程中最常被用求解最佳解的方法，但求解的过程相当地繁杂且耗时，而且经常因为限制条件和目标函的同，需要做同地设计，藉以提高求解的质量和效。本章将详细地介绍本研究所发展的启发式算法和分枝界限算法。31节先将本研究所用之符号作一完整的定义及明；32节将本研究所探讨之问题转换成学模式；33节针对所探讨的问题设计一启发式演算法；34节将介绍本研究所发展的分枝界限算法，其内容包括1分枝策2上限值3下限值4淘汰法则，以此作为求取最佳解的基准。31符号定义为于介绍后面的学模式和分枝界限算法，首先定义符号，并且进一步地明N总工件。MJ机器J,J1,2。PI,J工件I于机器J的作业处时间。SI,J工件I于机器J的开始处时间。TPI工件I的总处时间，即TPIPI,1PI,2。FMI工件I的加工顺序中所经过的第一部机器，即FMIM1ORM2。16I,K工件I与工件K形成工件对JOBPAIR，如图31所示，即在M1上，工件I位于工件K之前，而在M2上，工件K位于工件I之前。M1M2图31工件对I,K之示意图COSTIK工件I与K形成工件对所造成的配对成本，本研究将配对成本COSTIK设计如下COSTIK|PI,1PK,2|PK,1PI,2|。CI工件I的完工时间CMAX所有工件的最大完工时间，即CMAXMAXC。I1IN1,M1之工件处理顺序中工件I优先于工件K,IKYIK0,其它1,M2之工件处理顺序中工件I优先于工件K,IKZIK0,其它17IKKI32学模式二机续性工工厂总时程最小化的排程问题，可以下之整规划的模式表示目标函MINCMAX1限制式SI,2SI,1PI,1SI,1SI,2PI,2I1,2,NIFMIM1I1,2,NIFMIM223SK,1SI,1M1YIKPI,1SI,1SK,1MYIKPK,1SK,2SI,2M1ZIKPI,2SI,2SK,2MZIKPK,2SI,JPI,JCMAXSI,J0I,K1,2,NIKI,K1,2,NIK45I,K1,2,NIKI,K1,2,NIK67I1,2,NJ1,28I1,2,NJ1,29YIK,ZIK0,1I,K1,2,NIK10上述整规划模式之式1为目标函，即为本研究所要探讨的总时程CMAX最小化，限制式2与3为各项工件经过机器之顺序及续性限制，限制式4与5规范工件I和K于M1之处顺序，限制式6与7规范工件I和K于M2之处顺序，限制式8为CMAX之限制条件。其中，M为一极大的BIGNUMBER。针对一个N项工件的问题，此学模式共有2N22N个01整变，2N个非负实，4N2N个限制式。1833启发式算法本研究针对二机续性工工厂的排程问题发展一启发式算法，以期能迅速且有效地解决J2|NOWAIT|CMAX之大规模问题。此外，将启发式演算法所得之解，应用于分枝界限算法，以求取所需之起始上限值，以下针对启发式算法之设计与实介绍分别进明。331启发式算法之设计本研究所发展之启发式算法是以总时程最小化为目标，于任一生产NN排程中，其总时程可表示为MAXI1PI,1I1,I1PI,2I2，其中I1I2为M1M2的总闲置时间TOTALIDLETIME。因总工件处时间为固定之常，所以，总时程最小化与机器之总闲置时间最小化是相等的，因此，本研究针对各部机器之闲置时间最小化之观设计启发式算法。介绍启发式算法之前，首先针对本节所提之符号进明。以I,K表示M1之工件加工顺序中工件I优先于工件K，且工件I与K形成工件对。本启发式算法分为个部分，部分一是将N个工件分成个集合，将加工顺序为M1到M2的工件放到奇顺位工件之集合S0，将加工顺序为M2到M1的工件放到偶顺位工件之集合SE。将奇顺位工件集合的工件与偶顺位工件集合的工件进配对，形成工件对，将配对好的工件对进结合，以产生一部分排程。部分二是将未配对的剩余工件按FLOWSHOP的方式进排序，再将部分结合，以产生一完整的排程。部分一可分为个阶段，明如下阶段一考机器之闲置时间I1I2最小化的观，透过指派问题ASSIGNMENTPROBLEM之求解，将工件配对成工件对。将工件对I,K之配对成本COSTIK设为COSTIK|PI,1PK,2|PK,1PI,2|，19其中工件I属于奇顺位工件S0之集合，工件K属于偶顺位工件SE之集合。本研究用熟知的匈牙法HUNGARIANMETHOD求解此指派问题。阶段二主要的内容为结合工件对，藉此产生一部份的工件排程。即将指派问题所得之工件对应用到阶段二，逐步地将各个工件对与已经排定的部分排程进结合。将个工件对结合后可形成区块BLOCKBG,H,P,Q，将B与工件对I,K进结合，将产生种可能的排序A区块B优先于工件对I,K与B工件对I,K优先于区块B，针对上述种的结合情形，其结合后所缩减之闲置时间明如下。CASEA区块B优先于工件对I,KMIN|PQ,1PP,2|,|PI,1PK,2|,PQ,1PP,2PI,1PK,20,且IKSK012M1KKM2CASEBTYPE1I2S0,且I1S0KKK1KI1SKKM1M2TYPE2I1S0,且I2S0CASECKKKKM1I2SM2TYPE2I2S0,且I1S0CASEDKKKKM1M2TYPE3I1S0,且I2S0CASEEKKKKM1KKM2CASEFTYPE3I2S0,且I1S0KKKK图311部分排程SK之分34KI2SKI1SKKKKKKKKKKK1KI2SKK1K1KKK1CI为工件I的完工时间I1,2,N。SK为一已知之部分排程，当工件K1加入排程后，其工件之完工时间CK1及相关之机器闲置时间之计算，详述如下。CASEA部分排程SK属于TYPE1，机器之闲置时间I1S0，且I2S0，K1KKK分别探讨工件K1之加工顺序属于FMK1M1及FMK1M2之情形。CASEA1工件K1先经过M1，即FMK1M1，如图312所示。PK1,1K，其中KPK1,2PK,1，则工件K1之完工时间和机器之闲置时间分别如下CK1CK1PK1,2。12IK1SK1KPK1,1；IK1SK10。1IK1SK1M1M2APK1,1KM1M2BPK1,1K图312SK属于TYPE1且FMK1M1PK1,1K，则工件K1之完工时间和机器之闲置时间分别如下2CK1CKPK1,1PK1,2CK1IK1SK1PK1,2。12IK1SK1；IK1SK1PK1,1K035K1K1K2IK1SK1K1KK1K1K1KK1KK1CASEA2工件K1先经过M2，即FMK1M2，如图313所示。工件K1之完工时间和机器之闲置时间分别如下CK1CK1PK1,1PK1,2。1IK1SK1KPK1,2IK1SK10。2IK1SK11M1M2图313SK属于TYPE1且FMK1M2CASEB部分排程SK属于TYPE1，机器之闲置时间I2S0且I1S0。KKK1KCASEB1工件K1先经过M1，即FMK1M1，如图314所示。IK1SK11M1M2APK1,1KM11M2BPK1,1K图314SK属于TYPE1且FMK1M136K1K1K2IK1SKK1KK1K1K1KK1KK1K1K1KKK1K1PK1,1K，其中KPK1,2PK,1，则工件K1之完工时间和机器之闲置时间分别如下1CK1CK1PK1,2CKIK1SKPK1,1PK1,212IK1SK1KPK1,1；IK1SK10PK1,1K，则工件K1之完工时间和机器之闲置时间分别如下CK1CKPK1,1PK1,2CK1IK1SK1PK1,22IK1SK101IK1SK1PK1,1K2CASEB2工件K1先经过M2，即FMK1M2，如图315所示。工件K1之完工时间和机器之闲置时间分别如下1CK1CK1PK1,1PK1,2CKIK1SK1PK1,112IK1SK1PK1,2K；IK1SK10IK1SK11M1M2图315SK属于TYPE1且FMK1M2CASEC部分排程SK属于TYPE2，机器之闲置时间I1S0且I2S0。KKKKCASEC1工件K1先经过M1，即FMK1M1，如图316所示。PK1,1PK,2，则CK1CKPK1,2IK1SK1PK,2PK1,11IK1SK102PK1,1PK,2，则CK1CKIK1SK1PK1,22IK1SK101IK1SK1PK1,1PK,2237K1K1KK1KK1M1K1K1M2APPK1,1K,2M1K1K1M2BPPK1,1K,2图316SK属于TYPE2且FMK1M1CASEC2部分排序SK属于TYPE2又FMK1M2，则排序为K1,K12，用证明一之结果，将工件K,K1形成工件对，如图317所示。工件经过位移后得到完工时间和机器之闲置时间分别如下CKCKPK1,2；CK1CKPK,2PK1,111212IKSK1IKSKPK1,2；IKSK1IK1SK1IK1SK10。IKSK11图317SK属于TYPE2且FMK1M2CASED部分排程SK属于TYPE2，机器之闲置时间I2S0且I1S0。KKKKCASED1工件K1先经过M1，即FMK1M1，如图318所示。38KK1I2SKK1KK1I1SKK1PK1,1PK,2，则CK1CKPK1,2IK1SK1PK,2PK1,11IK1SK102PK1,1PK,2，则CK1CKIK1SK1PK1,22IK1SK101IK1SK1PK1,1PK,22I1SK1K1M1M2APPK1,1K,2M1K1K1M2BPPK1,1K,2图318SK属于TYPE2且FMK1M1CASED2部分排序SK属于TYPE2且FMK1M2，如同CASEC2将工件形成工件对，如图319所示。PI2S，则CCPPK1,2KKK1KK,2K1,1IK1SK101IK1SK1IKSKPK1,222PI2S，则CCPI2S；CCPPK1,2KKKKK1,2KKK1KK,2K1,1IKSK1PK1,2IKSKIKSK1IK1SK1IK1SK101221239KK1I2SKK1KK1KK1M12M2I2SAPK1,2KK1IKSK1M1M2I2SBPK1,2KK图319SK属于TYPE2且FMK1M2CASEE部分排程SK属于TYPE3，闲置时间I1S0且I2S0。KKKKCASEE1工件K1先经过M1，即FMK1M1，如图320所示。工件之完工时间CK1CKPK1,1PK1,2机器之闲置时间I1SI20SPPK1K1K1K1K,1K1,1M1IK1SK1M2图320SK属于TYPE3且FMK1M1CASEE2工件K1先经过M2，即FMK1M2，如图321所示。PK1,2PK,1，则CK1CKPK1,1IK1SK101IK1SK1PK,1PK1,22PK1,2PK,1，则CK1CKIK1SK1PK1,11IK1SK1PK1,2PK,11IK1SK10240KK12KK1KK1K1KKK1IK1SK1K1KM1K1K1M2APK1,2PK,1I1SK1K1M1M2BPK1,2PK,1图321SK属于TYPE3且FMK1M2CASEF部分排程SK属于TYPE3，闲置时间I2S0且I1S0。KKKKCASEF1工件K1先经过M1，即FMK1M1，如图322所示。工件之完工时间CK1CKPK1,1PK1,2机器之闲置时间I1S0I2PPSK1K1K1K1K,1K1,1M1IK1SK1M2图322SK属于TYPE3且FMK1M1CASEF2工件K1先经过M2，即FMK