可中断平行机排序问题.研究

《可中断平行机排序问题.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1．1排序问题第一章绪论排序(Scheduling)理论是研究如何在满足一定要求下，对需完成的任务进行合理安排使得到的结果在某种意义下达到最优，它有着重要的理论意义和广泛的应用背景．排序理论与理论计算机科学和离散数学结合紧密，并广泛应用到生产计划调度、信息处理、物流管理、服务行业等领域，这些新兴领域的蓬勃发展不仅使经典问题的研究不断深入，而且还涌现了许多有实际背景的新问题．自上世纪50年代人们开始研究排序问题至今，已有大量的排序文献发表在国内外的重要期刊上，可以说，排序研究已成为目前组合

2、优化领域最活跃的分支之根据排序研究的最初背景，我们通常把需要完成的任务称为工件Gob)，把完成任务需要的资源称为机器(machine)，我们希望找到一个可行的排序(schedule)，使得某个给定的目标函数达到最小(大)．这里的可行一般是指在同一时刻，一台机器至多加工一个工件，一个工件也只能在一台机器上加工，并且该排序满足问题特定的约束要求．描述一个排序问题可用所谓的“三参数表示法”(three-field把p把s饥talion)8伊一【261，其中n，p，，y分别代表特定的机器环境、工件特征和最

3、优准则．它们是排序问题的三个组成部分．机器环境用来描述机器的数量、不同机器之间的关系等与机器有关的性质．常见的机器系统包括单台机(singlemachine)、平行机(parallelmachines)、流水作qP(flowshop)、有序作qP(jobshop)和自由作盟k(openshop)等．在本文中，我们着重讨论平行机排序问题，即机器数至少为2，每个工件只需经过某台机器加工一次即可完成．根据机器的性能，可以把平行机分为三类：同型(identical)平行机：系统中所有机器的功能，效率完全一

4、样：同类(uniform)平行机：系统中机器有各自不同的加工速度，但任意工件在不同机器上的加工时间有相同的比例关系；不同类(unrelated)平行机：系统中机器各不相同，工件在不同机器上的加工时间比不全相同．在三参数表示法中，它们分别用P，Q，脓示．本文中主要考虑同型机和同类机两种机器．对一般的m台同类机，设舰的速度为＆，i=1，2，⋯，m．不失一般性，不妨设8l≤现S⋯≤‰．若只考虑2台机器同类机，我们假设1=slS52=乳若考第一章绪论虑m台同型机，则假设所有机器速度为1，即s1=82_．．

5、．=8rn,=1．工件特征一般可用工件的加工时间(也称为工件长度)，工件的释放时间，工件相互之间的依赖关系，工件加工时是否可中断等来刻划．根据排序者对工件信息的了解程度，又可将排序问题分为离线、在线和半在线等．如果排序者在排序开始前已知工件的全部信息，例如工件数，每个工件的加工时间等，则称该问题是离线(ofl]ine)的．反之，如果工件的信息是随着排序过程～个个地依次释放的．具体地说，只有在位于某个工件前的全部工件均被安排完毕后，排序者才能知道该工件的有关信息，而且工件一旦被安排就不能改变．这样的

6、排序问题称为在线(online)的．而半在线(semi．online)是指排序者掌握的信息位于在线和离线之间，我们将在后面的小节中详细讨论．所谓最优准则，通俗地讲，也就是以什么为目标函数．根据可行排序和工件的加工时问，我们可以算出某排序下工件m的完工时间。和机器舰的完工时间厶．称G。=m．axo为排序的最大完工时间(makespan)．称Ck。=m遗厶为最小机器负载．它们是本文中主要讨论的两个目标函数，前者为极小化目标，后者为极大化目标(该问题也叫机器覆盖(MachineCovering)f司题)

7、．文献中常见”的其他目标函数还有(赋权)总完工时间、最大延误时间、最大误工时间、最小误工个数等．有关排序问题的综述，可参看文献【8；661．1．2近似算法和竞争比分析所谓排序问题的算法(algorithm)是指一个预先制定的执行程序，对这个排序问题的任何一个具体的例子(简称为实例。instance)，按照这个程序操作后都可以得到一个可行的排序．解离线问题的算法称为离线算法，相应地，解在线问题的算法称为在线算法．例如LPT(LargestProcessingTnne)算法【25】和LS(ListSc

8、heduling)算法C24】分别是经典平行机排序问题的离线和在线算法．由于在离线问题中，排序者在排序前知道工件的全部信息，因此LPT算法先把所有工件按加工时间的非增序排成一列，然后依次将它们安排在能使其最早完工的机器上加工．而在在线问题中，在排序进行过程中后续工件信息是未知的，因此不可能将工件按加工时间大小排列，LS算法在极小化C-。时将工件按原来的顺序安排在能使其最早完工的机器上加工，而在极大化C_i。时则将工件按原来的顺序安排在能使其最早开工的机器上加工．将实例通过某种规则编