首页 | 本学科首页   官方微博 | 高级检索  
     检索      

带强制工期的可中断平行机排序问题
引用本文:钟雪灵,王国庆,程明宝,李晓春.带强制工期的可中断平行机排序问题[J].系统科学与数学,2011,31(7).
作者姓名:钟雪灵  王国庆  程明宝  李晓春
作者单位:1. 广东金融学院计算机系,广州,510520
2. 暨南大学管理学院,广州,510632
3. 广东工业大学管理学院,广州,510520
4. 华南师范大学南海校区,佛山,528225
基金项目:教育部人文社会科学研究项目基金(09YJC630088)
摘    要:讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.

关 键 词:平行机排序  强制工期  空闲时间  提前完工时间和  

PREEMPTIVE SCHEDULING WITH DEADLINES ON PARALLEL MACHINES
ZHONG Xueling,WANG Guoqing,CHENG Mingbao,LI Xiaochun.PREEMPTIVE SCHEDULING WITH DEADLINES ON PARALLEL MACHINES[J].Journal of Systems Science and Mathematical Sciences,2011,31(7).
Authors:ZHONG Xueling  WANG Guoqing  CHENG Mingbao  LI Xiaochun
Institution:ZHONG Xueling (Department of Computer,Guangdong University of Finance,Guangzhou 510520) WANG Guoqing (Department of Business Administration,Jinan University,Guangzhou 510632) CHENG Mingbao (School of Management,Guangdong University of Technology,Guangzhou 510520) LI Xiaochun (Nanhai Campus,South China Normal University,Foshan 528225)
Abstract:This paper discusses the problem that n jobs with their own deadlines have to be processed on identical machines considering the idle insert.The objective is to find a preemptive job sequence so as to minimize the total earliness.The complexity is considered firstly,and the problem is proved strongly NP-hard through the induction of 3-partition problem.Then, the special case of common deadline is discussed.Since tardy jobs are prohibited,it's possible that there is no feasible sequence for the problem.The f...
Keywords:Parallel machines scheduling  deadline  idle time  total earliness  
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号