两个带机器准备时间的半在线排序

研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.     

同型平行机上的在线分批排序问题

本文首次考虑了同型平行机上的在线分批排序问题,用三元素法表示为pm｜rj∈{0,r},B｜Cmax,并对这一问题给出了一个竞争比为8/3-2/3m的在线算法MBLPT算法．     

同型平行机上的在线分批排序问题

对同型平行机上的在线分批排序问题,进行分析的基础上,用三元素法表示为Pm｜rj∈{0,r）,B｜Cmax,并对这一问题给出了一个竞争比为8/3-2/2m的在线算法MBLPT算法。     

一类有尺寸大小的在线分批排序问题

研究了工件有尺寸大小的一致性在线分批排序．就所有工件有两个到达时间ri,i=1,2(不妨设r1=0,r2=r)对于0时刻到达的工件中加工时间最大的批满足一定的约束条件下的一致性在线分批排序给出一个在线算法,并证明了算法的竞争比不超过2．357．     

1|rj=bj-ajuj|∑uj+Cmax型受资源约束排序问题

给出1|rj=bj-ajuj|∑uj Cmax型受资源约束排序问题的概念及当问题任务排列确定时寻求最优资源分配的一个简单算法,初步探讨了该问题的最优排序.     

机器有两种不同速度的平行工件半在线排序研究

本文提出了新模型Q2m︱rj=0,on-line-ncv︱C max,并通过分析模型的特点,设计出了半在线算法,引进等效化(Virtualization)概念证明了当P≥m(s+1)max/(i∈τ)mjPj时(其中P为工件集的总负荷),算法的竞争比为2-s/(m(s+1)).     

有限重启的单机在线分批排序问题

研究了单机批容量b=3时有限重启且工件长度丰H同的情形,给出了一个竞争比为4/3的最好可能的在线算法.     

工件可选择的平行机在线排序

研究了一类平行机在线排序问题,且工件可以选择.用三参数法表示该模型为:Pm|on-line,rj,D|∑,fJ.其中D指机器使用期限,fj为工件Jj的加工利润,目标函数是使得在机器使用期限内所获总利润最大.本文给出了该模型fj=1情形(即工件费用相同)的所有在线g法竞争比的上界1/2,进而给出了两台机器、fj=1且工件序列只含两类工件情形(小工件加工时间为1,大工件加工时间为d≥2)的在线算法(ξ)1,其竞争比为1/2,为最具竞争性的     

带有霸王工件的单机在线分批排序

研究了一个带有霸王工件且允许重启的单机在线分批排序,其目标函数值为求时间表长．对于批容量无限的情况,给出了一个最坏竞争比为2的在线算法．     

一类带批安装时间的平行机在线分批排序问题

研究一类带批安装时间的平行机排序问题。工件按时间到达,在任何时刻,只知道当前已经就绪工件的信息。工件成批加工,同一批中工件的完工时间为批中最后一个工件的完工时间,每批开工前有一个固定的批安装时间。目标函数为极小化所有工件的总完工时间。主要考虑两个到达时间且工件加工时间都相等的特殊情形,给出竞争比为3/2的在线算法,并且有实例说明此界为紧致的。     

M台同型机极大化最小机器负载的半在线问题

In this paper, a semi on-line version on m identical machines M1, M2, …,Mm(m≥3) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m-1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2m-1)pmax where pmax is the largest job's processing time, then the worst-case ratio is 2-1/m.     

Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on mIdentical Machines

1　Introduction　In this paper, we consider a semi on line version onm identical machines M1, M2, …, Mm (m ≥3 )where the processing time of the largest job is knownin advance. A list (j1, j2, …, jn ) of jobs withprocessing times p1, p2, …, pn is given on line,which means we get the jobs one by one but both thetotal number of jobs that need to be scheduled and thesize of the jobs are not previously known. Theprocessing time of job ji becomes known only whenji-1 has…     

Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on m Identical Machines

In this paper, a semi on-line version on m identical machines M1 , M2, …, Mm ( m ≥ 3 ) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m - 1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2 m - 1 )Pmax where pmax is the largest job‘s processing time, then the worstcase ratio is 2 - 1/m.     

Algorithms for semi on-line multiprocessor scheduling problems

In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off-line or on-line environment. But in practice, problems are often not really off-line or on-line but somehow in between. This means that, with respect to the on-line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on-line ones. The authors studied two semi on-line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature. Project supported by the National Natural Science Foundation of China (Nos. 19701028 and 19971078) and National 973 Research Project of China.     

工件加工时间恶化问题的若干研究

主要研究关于工件加工时间恶化的若干问题,给出了最大完工时间问题的一些性质、总完工时间问题的算法和性质,并根据实际问题,设计了一些新模型,相应地给出了该问题所具有的性质及一些简单算法．     

Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines

INTRODUCTION Sequencing and scheduling are forms of deci-sion-making which play a crucial role in most manufacturing and production systems as well as in most information-processing environments, and also exist in transportation and distribution settings and in other types of service industries. A scheduling problem is called on-line if it re-quires scheduling jobs irrevocably on the machines as soon as they are given, without any knowledge about jobs that follow later on. If we have full…     

单机主次指标排序问题1||T_(max)|∑U_j的P子问题

研究了单机主次指标排序问题1||Tmax|∑Uj。在工件LPT序与EDD序一致的情形下,给出了该问题的一个多项式时间可解的子问题。