有使用限制的两台机器排序问题的近似算法  

Approximation algorithms for two-machine scheduling with an availability constraint

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

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

出　　处：《华中师范大学学报（自然科学版）》2015年第1期11-13,20,共4页Journal of Central China Normal University：Natural Sciences

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

摘　　要：研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS(fully polynomial-time approximation scheme).A two-machine scheduling problem in which one machine has an availability constraint and the other is always available is studied in this paper.The objective is to minimize the makespan.Each machine can process at most one job at a time.Preemption is not allowed.An FPTAS（fully polynomial-time approximation scheme）is Presented.

关 键 词：排序 使用限制 算法 FPTAS 

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