一类加工时间依赖资源的单机排序问题

《一类加工时间依赖资源的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一类加工时间依赖资源的单机排序问题1．3排序问题的三参数表示法本文所讨论的排序问题都是用aI卢ly三参数表示法来描述的。1967年Conway等首先提出了用四个参数来表示排序问题。1979年Graham、Lawler和RinnooyKan等提出改用三个参数。下面要介绍的就是目前国际上使用的盘f∥『y三参数表示法。1．参数a=吼a2描述机器的情况。参数％∈形，P，Q，R，O，F，J)描述机器的类型：萨(≯可以省略)表示单台机器P表示同型号机器(同速机)Q表示同类型机器(恒速机)R表示不同类型机器(变速

2、机)0表示自由作业机器(开放作业)F表示流水作业机器(同顺序作业)L，表示有序作业机器(异顺序作业)参数口：∈(≯，，K}反映机器的数目：≯(≯可以省略)表示机器的数耳不指定，可以是任意正整数。2．参数∥表示工件或工件的性质、加工要求和限制，资源的种类、数量和对加工的影响等约束条件，它可以包含很多项，可能的项主要有：■表示工件有不同的准备时间或到达时间。如果不出现r，，说明，，=0；s，表示在工件t，．之前的安装时间(setuptime)；d．表示工件有不同的完工时间限制，即工期：prmp表示允许中

3、断抢先加工；prec、chains、tree表示工件的相关性：prec表示一般优先约束，chains表示优先关系是链状的，tree表示优先关系是树状的，又分为intree(入树)和outtree(出树)两类。nwt(no—wait)指被加工的工件不允许在两个相邻的机器之间等待。GT表示成组加工问题中同组工件连续加工。随着排序问题的不断发展，D的内容也在不断的发展变化，如在线问题、成组加工问题(不仅包括确定各工件组之间的加工顺序，而且需要确定同组中每个工件之间的加工顺序)及本文主要讨论的工件的加工时间

4、依赖于开工时间的问题等等。一3一类加工时间依赖资源的单机排序问题3．参数y表示目标函数，排序的目标是一个一维实数。通常是考虑所谓的正则(regular)目标，即满足：(1)目标函数是求最小值，(2)至少有一个工件的完工时间减少时，目标函数值才会减少。比较常见的目标函数有：C⋯：最大完工时间∑q：总完工时间∑w，C．：加权总完工时间上。。：最大延误时间∑乃：总误工时间∑吩0：加权总误工时间∑％娠瑰旷∞≥∑wjU．：加权总误工数等类似于多目标规划，形式上提出多目标排序并不难，国内外己进行研究。多目标排序

5、起步较晚，成果还不多。然而，早在1956年w．E．Smith在提出WESPT(weightedshortestprocessingtime)排序的同时，就研究过在没有工件误工的，所谓完美的(perfect)排序中搜索一个流程最小的排序问题，并得出搜索此种最优解的Smith规则。1．4排序问题的应用背景和研究状况在累积型(cumulative)排序问题中，资源约束排序问题是一种很普遍的问题，资源约束排序问题是在经典排序问题的基础上发展起来的，被很多人广泛的研究过，尤其是近年来，无论是理论研究还是实际应

6、用中都得到了广泛的重视。这是由于在生产管理领域中，有大量的问题都可以看成是资源约束的排序问题，研究这类问题有很大的指导实践的价值。资源约束排序问题对采用JIT(．1uStInTime)方式生产(即准时化生产)的企业尤为重要，这是因为，为了降低成本、简化计划、避免生产过量，JIT系统不设仓库，企业在接到定单后才进行生产，这样为了按期交货并节省——4——一类加工时间依赖资源的单机排序问题资源，安排生产就成了一个典型的资源约束排序问题。而在理论研究中，资源约束排序问题同样吸引着学者们的注意力，因为有很多经

7、典的最优化问题都是资源约束排序问题的特例。各种确定的资源约束排序问题包括以下几个方面内容：(1)一组有一定总量的资源(2)一组给定期限的不可中断的加工工序(3)各工序间的优先限制关系(4)各道工序需要各种资源的数量(5)完工的最后截止期限研究资源约束排序问题就是要找到工件的一个不可中断加工顺序，即各个工件的开始加工时间使得这个加工顺序能够满足资源量的约束，并且使目标函数极小化。对于离散型资源排序问题已有了非常丰富的成果，[4]中分别给出了四个两台同速机极小化最大完工时间的离散型资源约束问题，均是多项

8、式时间内可解的。而三台同速机极小化最大完工时间、有两种或三种资源且每一种资源有1个单位的数量，每个工件对每种资源的需求最多是1个单位的离散型资源约束问题，均为ⅣP难。[5]中给出两台同速机极小化最大完工时间仅有～种资源、数量和工件对资源的需求是任意的，且工件加工时间为l的离散型资源约束问题在O(nlogn)时间内可解，而三台同速机的该问题却是强NP难的。三台同速机极小化最大完工时问、仅有一种资源，该资源有1个单位的数量，每个工件对每种资源的需求最多是1个单位的离散型资