关于重新排序问题的研究

【作者】 慕运动；

【导师】 原晋江；

【作者基本信息】 郑州大学 ， 基础数学， 2007， 博士

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

【Abstract】 Scheduling is to allocate some jobs or tasks to some machines under a limited condition according to time order, and in order to optimize some objectives.Rescheduling is one of significant modern scheduling models and it is motivated by important applications. The problem of rescheduling in the face of dynamically arriving orders is faced constantly by manufacturing companies. The manufacturing companies have been made their production schedules in earlier according to their planes or some customers’ call, and schedule the jobs by some rule to optimize some objective. However it frequently happens that additional orders arrive after a schedule has been developed. These orders must then be integrated into the schedule so as to optimize some measure of system performance without causing undue disruption in the shop. Based on some researches, Hall and Potts （2004） studied the problem of rescheduling and introduced the conception of disruptions. They considered the rescheduling problem to minimize the maximum lateness and total completion time under a limit on the disruption constraints.Multicriteria scheduling, as a way of multi-objective decision-making, plays an important role in solving complicated problems arising from economics, administration, engineering, etc.. For example, a factory administrator needs to arrange the jobs to be processed such that the total completion time is minimized firstly to reduce the processing cost and the tardy jobs are limited to a lowest level secondly, and to satisfy the clients. Multicriteria scheduling includes lexicographical optimization or hierarchical optimization, Pareto optimization and composite objective function optimization.On-line scheduling is a modern scheduling model, in which the job information may not be known in advance. A job becomes available for processing at its arrival time, and its processing time only becomes known upon its arrival. Once the jobs have been scheduled, the states of the jobs cannot be changed. In the off-line scheduling, the information of all jobs has been completely known in advance. The performance of an on-line algorithm is described by its competitiveness, i.e. the ratio of the result of the on-line algorithm and the optimal value of the off-line situation for the same jobs. Exactly, for the problem of minimizing objective, the competitive ratioρof an on-line algorithm is defined as the supremum of the ratio of C and C₀, where C and C₀ are the objective of scheduling obtained by the on-line algorithm and an optimal off-line algorithm, respectively.This paper includes four parts. In the first part, some spacial solvable cases of rescheduling models are considered （Chapter 2）. In the second part, the new rescheduling models are studied （Chapter 3）. In the third part, multi-criteria rescheduling models are discussed （Chapter 4）. In the last part, on-line rescheduling problems are presented （Chapter 5）.In Chapter 2, the following results are developed. （1） The rescheduling problem to minimize the maximum lateness or the total completion time under a limit on the disruption constraints when d_j, p_j are compatible or the original jobs are fixed order are solvable in polynomial time or pseudo-polynomial time. （2） The rescheduling problem to minimize the total tardiness under a limit on the disruption constraints when p_j = p or d_j = d are solvable in polynomial time or pseudo-polynomial time. （3） The rescheduling problem for jobs on a single machine to minimize total weighted completion time under a limit on the maximum disruption when p_j and w_j of the jobs are anticompatible are solvable in polynomial time or pseudo-polynomial time.In Chapter 3, the following results are developed. （1） The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the maximum sequence disruption is solvable in polynomial time. （2） The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the total sequence disruption can be solved in polynomial time. （3） The rescheduling problems for jobs on a single machine with release dates to minimize makespan under a limit on the maximum time disruption or the total time disruption are strongly NP-hard.Chapter 4 studies the multicriteria rescheduling problems. In this parts, the disruptions of the original jobs are regarded as an objective in the same as classical objectives. The rescheduling problems of hierarchical optimization, Pareto optimization and linear composite objective function optimization between the classical scheduling cost (such as C_max, L_max,∑w_jC_j) of all the jobs and the degree of the disruptions (D_max（π^*）,Δ_max（π^*）,∑D_j（π^*）,∑Δ_j（π^*）) are considered. For some problems, we provide a polynomial or pseudo-polynomial time algorithm.Chapter 5 discusses the on-line rescheduling problems. In this parts, the original jobs have been arrived and sequenced by some rule, the new jobs arrive over time. For the online rescheduling problem to minimize the maximum lateness under a limit on the disruption constraints, a 2-competitive ratio algorithm is presented. For the online rescheduling problem to minimize makespan under a limit on the disruption constraints with release date, some |-competitive ratio algorithms are presented.更多还原