东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2006, Vol. 27 ›› Issue (7): 728-730.DOI: -

• 论著 • 上一篇    下一篇

工件具有区间限制的批在线调度

霍满臣;唐立新;   

  1. 东北大学信息科学与工程学院;东北大学信息科学与工程学院 辽宁沈阳110004;辽宁沈阳110004
  • 收稿日期:2013-06-23 修回日期:2013-06-23 出版日期:2006-07-15 发布日期:2013-06-23
  • 通讯作者: Huo, M.-C.
  • 作者简介:-
  • 基金资助:
    国家杰出青年科学基金资助项目(70425003);;

On-line batchwise workpiece scheduling with restriction of time interval

Huo, Man-Chen (1); Tang, Li-Xin (1)   

  1. (1) School of Information Science and Engineering, Northeastern University, Shenyang 110004, China
  • Received:2013-06-23 Revised:2013-06-23 Online:2006-07-15 Published:2013-06-23
  • Contact: Huo, M.-C.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

699

摘要： 研究同构并行机上的批在线调度问题,目标函数是使最大完成时间(最后一个工件的完成时间makespan)最小.工件以批方式到达且每个批中有m个工件,每个工件的加工时间随其批的到达而给定且限定在某个时间区间上.当一批工件到达时,在对其后批的信息不了解的情况下,要立即对该批中的工件进行调度,调度过程中不允许中断.针对这一问题,给出了一个批在线启发式列表调度算法,在同一批中的工件按LPT规则调度,当一批中的全部工件被调度完后,调度下一批中的工件.对算法的最坏情况进行了分析并给出了算法的竞争率.

关键词: 批在线列表调度, 竞争率, 同构并行机, 批工件列, 最大完成时间, 加工时间

Abstract: Studies the problem of on-line batchwise workpiece scheduling on m identical parallel machines of which the objective is to minimize the makespan, i.e., the time for finishing the last workpiece in a batch. In such a case all the workpieces arrive in batches and each batch has exactly m workpieces to which the processing time required for each one depends on the time the batch containing it just arrives. It supposes that the processing time be restricted in a time interval. When a batch of workpieces arrives we shall schedule them immediately without interruption though no information is provided for subsequent batches. An on-line heuristic listing algorithm for batchwise workpieces scheduling is thus proposed according to LPT rule by which the workpieces in next batch will be scheduled immediately if all workpieces in a batch have already been scheduled. The worst case was analyzed with the competitive ratio given.

中图分类号: