【作者】 柏庆国；

【导师】 张玉忠； 姜同松；

【作者基本信息】 曲阜师范大学 ， 运筹学与控制论， 2005， 硕士

【摘要】 排序论又称时间表理论,其作为运筹学的一个分支,作为一门应用科学,有着深刻的实际背景和广阔的应用前景。而其中的在线分批排序以及带机器准备时间的半在线问题,因其明显的实际意义,吸引了国内外许多学者。本文主要研究了这两类问题。 论文分三章来叙述。 第一章是引言,主要介绍了排序的生产背景发展、及其一些相关的基本知识。 第二章主要研究了工件有尺寸的单机在线分批排序(三元素表示法表示为1|r_j,B,s_j|C_max)及同类机在线分批排序(Q_m|r_j,B|C_max)。对于这两类问题,目前很少有人涉及。工件有尺寸的单机在线分批排序是指工件不但有不同的加工时间而且有不同的尺寸。假定机器的尺寸为B,若工件J_j的尺寸（s_j）大于B/2则称此工件为大工件否则称为小工件。若每一大工件的加工时间不小于任何一小工件的加工时间则称此问题为工件加工时间和工件尺寸一致的排序问题,简称一致性排序。 本章第一部分我们将分批时只考虑工件个数的单机在线分批排序问题（[25]）推广到工件有尺寸且所有工件有两个到达时间的一致性单机在线分批排序问题,并且给出了一个竞争比不超过33/14的算法。 第二部分讨论了工件有尺寸的一般情形的单机在线分批排序问题并给出了一个竞争比不超过161/60的算法。 本章最后对于分批时只考虑工件个数的单机在线分批排序问题（[25]）推广到m台同类机的情形,设计了一个在线算法并证明了此算法的竞争比为1+sum from i=1 to m-1 b_i/b_m。 第三章讨论了两台机器上知道工件的最大加工时间和工件加工时间总和两种半在线模型,此时目标函数是极小工件完工时间。用三元素法可表示为P₂,a_j|P_max|更多还原

【Abstract】 Scheduling, as a branch of the operations research and an applied sciences, has its profound practical and broad applied prospect, among which on-line batch-scheduling and semi on-line scheduling with available times have attracted the attention of so many scholars at home and abroad because of their obviously factual meanings. In this paper we mainly deal with these two kinds of problems.Three chapters are included in this thesis.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we mainly study the problem of on-line batch scheduling on a single machine with jobs having non-identical sizes to minimize makespan and the problem of on-line batch scheduling on uniform machines. Few are involved in these two kinds of problems at present. For the problem 1|r_j,B, s_j|C_max, each job has both processing time and size. We denote the machine capacity by B, a job is called a large one if its size is greater than B/2 , otherwise it is a small job. A batch processing problem is said to satisfy the proportional assumption if the processing time of each large job is not less than that of any small one.In the first part of this chapter, we extend the on-line batch scheduling on a single machine which considers only the number of jobs while forming a batch to one for which each job has a size and all jobs are due to two release time. Furthermore, we provide an on-line algorithm under proportional assumption更多还原