单台机器有使用限制的排序问题  

Single Machine Scheduling with an Availability Constraint to Minimize Makespan

作　　者：李刚刚[1] 李浩[2] 

机构地区：[1]华东理工大学理学院数学系,上海200237 [2]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《河南师范大学学报（自然科学版）》2014年第4期18-21,共4页Journal of Henan Normal University(Natural Science Edition)

基　　金：国家自然科学基金(11126284)

摘　　要：研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.In this paper, the problem of scheduling jobs on a single machine with an availability constraintto minimize makespan is considered. Each job has a release time. Jobs can be processed on the machine only after their release times. Pre- emption is not allowed. For the offline version, a 4/3-approximation algorithm and a dynamic programmingare provided, re- spectively. For the online version, an optimal online algorithm is presented.

关 键 词：排序 动态规划 使用限制 算法 

分 类 号：O223[理学—运筹学与控制论]