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

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

项目编号： No.61303010

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 曹茜

作者单位： 上海电力学院

项目金额： 23万元

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

中文关键词： 在线；半在线；排序调度；缓冲区；时间表长

英文摘要： 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.

英文关键词： online；semi-online；scheduling；buffer；makespan