缓冲区长度有限的平行机在线调度模型及算法分析

In this project we consider online scheduling on parallel machines with a limited-size buffer. Assume that there exists a buffer with limited size and the jobs arrive one by one in terms of a given list. The current job can be either assigned to a machine or put in the buffer. In the latter case, if the number of all jobs in the buffer reaches the upper bound of the buffer's size, then one of the jobs in the buffer must be assigned to a machine immediately. We will focus on the models of online scheduling on identical machines and uniform machines. When the number of machines is not less than three, the model of online scheduling on identical machines with a limited-size buffer has been not studied by researchers now. Such as the online scheduling problem on m identical machines with a limited-size buffer. Refer to the related model of online scheduling on two uniform machines, we propose several problems firstly。 For example, the online scheduling problem on two uniform machines with a limited-size buffer and known maximum job size, or jobs arriving in decreasing order of their processing times, etc. Furthermore, we will summarize the more valuable models in order to fill up the blank under the situation with a limited-size buffer.

本课题研究缓冲区长度有限的平行机在线调度模型。假设在机器之外存在着一个长度有限的缓冲区，工件按照一个给定列表的顺序依次到达，到达后可以马上安排在某台机器上加工，也可以先将其暂时放在缓冲区中。当缓冲区存放的工件数到达其长度上限时，新到达的工件如果需要放在缓冲区中，则缓冲区中的某一个工件必须取出并立刻在某台机器上加工。 我们将重点考虑相应的同型机和同类机在线调度模型，其中对于缓冲区长度有限的机器数量不小于三台的同型机在线调度模型的研究，比如缓冲区长度有限的m台同型机在线调度问题，是前所未有的工作。而对于相应的两台同类机在线模型，我们初步提出了几个问题，即已知工件最大加工时间且缓冲区长度有限的两台同类机在线调度问题、已知工件按照加工时间非增序到达且缓冲区长度有限的两台同类机在线调度问题等。进一步我们将总结出更有价值的调度模型，填补缓冲区长度有限情况下调度理论研究的空白。

本课题主要研究缓冲区长度有限的平行机在线调度模型，与本课题相关的研究工作主要可以分为两个方面：平行机在线调度模型和缓冲区长度有限的在线调度模型。我们在这两个工作方面都取得了一定的进展，尤其在第一个方面“平行机在线调度模型”上取得了较重要的进展。. 对于第一方面，我们首先研究了已知工件按加工时间的非增序到达且所有工件的加工时间长度有界的两台同型机的半在线排序调度问题，目标是最小化时间表长。我们证明了问题的下界并给出了最优的算法。. 然后研究了所有工件加工时间是有界的两台同类机半在线排序调度问题，我们对问题构造了一些下界，同时证明了LS算法在关于参数s和t的大部分区间范围内为最优算法，进一步设计了两个在某些区间内的最优算法。. 接着考虑了已知每个订单的总加工时间都相同的两台同型机在线排序调度问题，对于这个问题我们考虑订单数不小于B(B为不小于2的正整数)的情况。我们给出了与参数B有关的下界，然后我们将B分为偶数和奇数讨论，分别设计了两个最优算法。. 最后考虑了每个订单中的工件加工时间有界且最大工件加工时间都相同的两台同型机在线排序调度问题。同样也考虑订单数不小于B的情况，我们给出了与参数B和t有关的下界，并设计了最优的算法OBt。 . 对于第二方面，我们首先考虑了带缓冲区的所有工件的加工时间有界且已知最大工件的加工时间的两台同型机半在线排序调度问题，目标是最小化时间表长。我们构造了问题的关于参数t的一些下界；同时研究了所有工件的加工时间有界且已知最大工件的加工时间和最优解值的两台同型机半在线排序调度问题，我们同样给出了与参数t有关的问题的下界，然后在一个区间内设计了一个性能较好的近似算法OBM。