| 单台机器有使用限制的排序问题 |
| |
| 引用本文： | 李刚刚,李浩.单台机器有使用限制的排序问题[J].河南师范大学学报(自然科学版),2014(4):18-21. |
| |
| 作者姓名： | 李刚刚 李浩 |
| |
| 作者单位： | 华东理工大学理学院数学系;河南师范大学数学与信息科学学院; |
| |
| 基金项目： | 国家自然科学基金(11126284) |
| |
| 摘 要： | 研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.
|
| 关 键 词： | 排序 动态规划 使用限制 算法 |
Single Machine Scheduling with an Availability Constraint to Minimize Makespan |
| |
| LI Ganggang;LI Hao.Single Machine Scheduling with an Availability Constraint to Minimize Makespan[J].Journal of Henan Normal University(Natural Science),2014(4):18-21. |
| |
| Authors: | LI Ganggang;LI Hao |
| |
| Institution: | LI Ganggang;LI Hao;Department of Mathematics;School of Science,East China University of Science and Technology;College of Mathematics and Information Science,Henan Normal University; |
| |
| Abstract: | 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.Preemption is not allowed.For the offline version,a 4/3-approximation algorithm and a dynamic programmingare provided,respectively.For the online version,an optimal online algorithm is presented. |
| |
| Keywords: | scheduling dynamicprogramming availability constraint algorithm |
| 本文献已被 CNKI 等数据库收录！ |
