平行机上带有前瞻区间的不相容工件组在线排序问题

作     者：李文华 柴幸 袁航 杨素芳 LI Wenhua;CHAI Xing;YUAN Hang;YANG Sufang

作者机构：郑州大学数学与统计学院郑州450001 浙江大学经济学院杭州310027 

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2015年第19卷第4期

页      面：121-126页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金(No.11171313) 河南省教育厅科技研究重点项目(No.14A110025) 郑州大学自主创新项目(No.14LD00610) 

主　　题：在线排序 平行分批 不相容工件组 最大完工时间 竞争比 

摘      要：研究当不相容工件组的个数与机器数相等时，具有前瞻区间的单位工件平行机无界平行分批在线排序问题工件按时在线到达，目标是最小化最大完工时间．具有前瞻区间是指在时刻t，在线算法能预见到时间区间（t，t＋β[]内到达的所有工件的信息．不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工．当β≥1时，提供了一个最优的在线算法；当0≤p〈1时，提供了一个竞争比为1＋α的最好可能的在线算法，其中＆是方程OL0＋（1＋β）α＋β-1=0的一个正根．最后，给出了当β=0时稠密算法竞争比的下界，并提供了达到该下界的最好可能的稠密算法．