文献类型：期刊文献

中文题名：单台机器有使用限制的排序问题

英文题名：Single Machine Scheduling with an Availability Constraint to Minimize Makespan

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

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

年份：2014

卷号：42

期号：4

起止页码：18

中文期刊名：河南师范大学学报（自然科学版）

外文期刊名：Journal of Henan Normal University(Natural Science Edition)

收录：CSTPCD;;北大核心:【北大核心2011】；

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

语种：中文

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

外文关键词：scheduling; dynamicprogramming; availability constraint; algorithm

摘要：研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为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.