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

东北大学学报(自然科学版) ›› 2013, Vol. 34 ›› Issue (5): 628-631.DOI: -

• 信息与控制 • 上一篇    下一篇

锁定初始调度的紧急工作单机重调度问题

郭艳东，黄敏，王庆   

  1. (东北大学流程工业综合自动化国家重点实验室，辽宁沈阳110819)
  • 收稿日期:2012-10-17 修回日期:2012-10-17 出版日期:2013-05-15 发布日期:2013-07-09
  • 通讯作者: 郭艳东
  • 作者简介:郭艳东(1981-)，女，辽宁锦州人，渤海大学讲师，东北大学博士研究生；黄敏(1968-)，女，福建长乐人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(71071028，70931001，71021061，61070162，71171040)；国家杰出青年科学基金资助项目(61225012)；高等学校博士学科点专项科研基金优先发展领域课题(20120042130003)；高等学校博士学科点专项科研基金资助项目(20110042110024，20100042110025)；工信部物联网发展专项资助项目；中央高校基本科研业务费专项资金资助项目(N110204003).

Rescheduling for Rush Jobs on Single Machine with Loads Locked Original Scheduling

GUO Yandong， HUANG Min， WANG Qing   

  1. State Key Laboratory of Synthetical Automation for Process Industries， Northeastern University， Shenyang 110819， China.
  • Received:2012-10-17 Revised:2012-10-17 Online:2013-05-15 Published:2013-07-09
  • Contact: WANG Qing
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

604

摘要： 对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间，目标为最小化初始工作的等待时间和；重调度目标是在初始调度锁定的情况下，将紧急工作插入初始调度，最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型，然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法，并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.

关键词: 重调度问题, NP难, 紧急工作, 启发式算法, 等待时间

Abstract: Rescheduling problem for rush jobs on single machine was researched. Due to the reason that the original scheduled jobs have release time， a formulate RRLS(rescheduling rush jobs with loads locked on single machine) problem was proposed based on the following measures. That is， the total waiting time was minimized， and the rush jobs was inserted into original schedule， and the maximum waiting time was minimized with loads locked. Then the RRLS problem was proved as a NPhard one. A heuristic algorithm was presented according to the property of the problem， and its time complexity was also given. At last， an example proved the optimality conditions of algorithm.

Key words: rescheduling problem, NPhard, rush jobs, heuristic algorithm, waiting time

中图分类号: