具有资源约束的排序问题

《具有资源约束的排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一节引言排序(scheduling)f司题是一类重要的组合最优化问题，它是利用一些处理机(processor)、机器(machine)和资源(resource)，最优地完成一批给定的任务(task)或作业00b)．在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工时间的影响等．最优的完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短，如最大完工时间，处理机的利用率，如完工时间和等的描述．排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域．从普通的生产部门的计划安排、

2、人员调度，学校课程表的制订，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法．由于具有广泛的应用背景，排序问题越来越得到广泛关注，对排序问题的许多研究结果可以被应用到形形色色的生产与服务行业当中．在国内，早在20世纪60年代中科院越民义教授就注意到排序问题的重要性和在理论上的难度．1960年，他编写了国内第一本排序理论讲义．70年代初他和韩继业一起研究同顺序流水作业排序问题，他们发表在《中国科学》上的著名论文[35]开创了中国研究排序论的先河，在他们两位的倡导和带动下，国内的排序理论研究和应用研究有了较大的开展，例如文献[36]，[37]就是典型代表．国际上普

3、遍认为1954．1一第一节引言年Johnson的论文[2]是排序论的第一篇文章[1]，从这篇论文问世以来的半个世纪中全世界已经发表排序文献2000多篇[37]，这些排序的论文和书籍中绝大部分是在过去的10年中发表的，排序论的长足发展，特别是新型排序的丰硕成果，使排序论成为发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领域之一．目前主要使用生产加工业作业计划排序的术语来表述排序问题．由于处理机的数量和种类，工件或作业的顺序、到达时间、完工限制，资源的种类和性能等情况是错综复杂的，导致排序问题的类型有成百上千种，有关排序问题的文献也是浩如烟海．Lawler等在[1】

4、中详细讨论了在一些基本的机器资源配置环境与工艺要求下的排序问题：加工车间环境方面的单阶段(SingleStage)与多阶段(MultiStage，如Flowshop、Jobshop、Openshop)、每个阶段的单处理机(SingleMachine)与平行机(ParallelMachines，如Identical、Uniform、Unrelated)、可用机器数量是给定(Constant)还是参数可变(Arbitrary)等；待加工工件是否允许加工中断(Preemptive)、加工顺序(Precedence)方面的要求、就绪时间是否相同、有无交货期限制等等；以及排序优

5、化目标的不同．文献中其它常见的排序约束有：工件具有可与加工时问分离的顺序相关或否的单件及成组加工调整(Setup、BatchSetup)时间(参见[3】)、工件有限容量批量加工(参见[4】)、两道工序问Buffer容量限StJ(Finite、Infinite)、工件在连续两道工序间不许等待(No．wait)(参见[5】)等等不一而足．．2一第一节引言上面谈到的排序问题都是确定性的单优化目标的排序问题，含随机参数的排序问题可参考[1】，多目标排序问题的文献比较少见；另外，这里的资源约束主要是机器资源方面的，涉及其它种类资源约束的排序(ResourceConstraine

6、dScheduling)Ih]题是现实中较为常见的．例如，数控机床在加工零件时，除了数控机床作为机器资源外，还需要电力、人力、消耗的原材料等各种资源．从对资源的种类需求上分类具有资源约束的排序问题可分为单资源约束和多资源约束排序问题，从资源的供给方式上又可分为离散(discretely)资源和连续(con—tinuous)资源排序问题，从资源的使用性质上又可分为可再生的(re．newable)和不可再生的(nonrenewable)资源排序问题等等．对排序问题的研究，有一个基本思路，那就是：应用或借鉴求解其它组合最优化问题的方法，充分利用排序问题本身的特殊性质，以确定

7、满足约束条件的最优排序．对具有多项式时间算法的排序问题，要尽可能地找出空间复杂性和时间复杂性较好的算法．对于还不知道是否有多项式算法的排序问题，要用复杂性理论进行分析．对NP．难问题的求解：一是用分支定界法、动态规划等巧妙的穷举法求出它的精确最优排序，这类算法计算量大，只对小规模的问题才是可行的；另一种方法是求出它的近似最优排序，各种局部搜索法和启发式算法都是很有效的，这类算法计算量小，并能满足一定的实际需要．尽管排序问题花样百出，各类文献中的排序问题建模却大多是基．3．第一节引言于Shop模型和平行机模型，常采用Graham等于1979年在[6】中