论文部分内容阅读
排序就是在一定的约束条件下对若干个要加工的工件或任务在指定的机器上按时间进度进行分配和调度,使某一个或某一些指标达到最优。
重新排序问题是一种新型的排序模型.它有着重要的实际应用背景.生产部门根据自己的生产计划或是由客户提出的要求,在生产前一定时期内事先有一个作业方案,将已有的任务或订单按照某一规则安排好,使某一目标值最优.但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达.这时就要把新的任务和原有的还未加工的任务一起加工.为了不失信于对原客户的承诺或耽误原任务的完成,这就要求在原有的工件或任务的次序不至于打乱的过多的前提下,使得总的目标函数值达到最优.Hall和Potts(2004)在前人研究的基础上,系统地研究了重新排序问题.他们引入了序列错位(sequence disruption)和时间错位(time disruption)的概念,研究了在原来最优排序和任意排序的基础上重新排序,在原来排序的序列错位和时间错位不至于太大的情况下,使目标函数最优的问题。
多目标排序作为一种多目标决策,在解决经济、管理、工程、军事等领域出现的复杂问题中起着越来越重要的作用.例如,在一个工厂的生产过程中,生产决策者不但想要使工件的总完工时间最小以减少生产费用,还要尽量使误工工件的个数最少,以更好地满足顾客的要求.多目标排序包括字典序最优问题、Perato最优解问题和组合目标函数最优问题。
在线排序是指每个工件的信息在该工件到达之前是未知的.在工件的到达时间得到该工件的所有信息并允许对该工件进行加工;而且一旦决定工件的安排就不允许改变.而离线排序在安排所有工件之前便知道所有工件的信息.衡量一个在线排序算法最常用的指标是它的竞争度(competitiveness),即把在线排序算法的结果与对相同工件运用离线排序算法得到的最优排序的结果进行比较.更确切的说,我们用竞争比(competitive ratio)ρ来衡量一个在线排序算法的性能.对于使目标函数为最小的在线排序问题,竞争比ρ定义为对问题的所有实例的比值C/C<,0>的上确界,其中C和C<,0>分别表示由这个在线排序算法得到的目标函数值和相应的离线排序的最优值。
本文的内容分四部分:第一部分研究了几种特殊情形的重新排序模型(第二章).第二部分研究了一种新型重新排序模型(第三章)。第三部分研究了多目标的重新排序问题(第四章).第四部分研究了在线的重新排序问题(第五章)。
在第二章中,研究了几种特殊情形的重新排序模型,其主要结果如下:对一些未解问题和强NP-困难问题, (1)给出了当工件的加工时间与工期相容或原始工件保持其相对顺序时,使得最大延迟和加工时间和为最小的多项式或拟多项式时间算法;(2)给出了当工件具有相同的加工时间或具有相同的工期时,使得误工和为最小的多项式或拟多项式时间算法; (3)给出了当工件的加工时间与权重反相容时,使得加权完工时间和为最小的多项式或拟多项式时间算法。
在第三章中,对于具有到达时间的最小化最大完工时间的重新排序问题,(1)给出了在最大序列错位约束下的最小化最大完工时间的重新排序问题的多项式时间算法; (2)给出了在总序列错位和约束下的最小化最大完工时间的重新排序问题的多项式时间算法; (3)证明了在最大时间错位或总时间错位约束下的最小化最大完工时间的重新排序问题是强NP-困难的。
在第四章中,对于多目标的重新排序问题,本文将错位量作为第二目标来考察,研究了四种错位量(D<,max>(π<*>),△<,max>(π<*>),∑D<,j>(π<*>),∑△<,j>(π<*>))与传统的目标函数(如C<,max>,L<,max>,∑w<,j>C<,j>)的相互组合问题,给出了多目标排序中字典序最优问题、Perato最优解问题和线性组合目标函数最优问题的多项式时间算法或拟多项式时间算法。
在第五章中,主要研究了在线重新排序问题.即在原始工件已经按照某一规则排好,而新工件在原始工件的加工过程中是按时间顺序到达的.在此情形下,本文分别给出了在各种错位量约束下,目标函数为最小化最大延迟的竞争比为2的在线排序算法和最小化最大完工时间的竞争比为3/2的在线排序算法。