Single machine scheduling with semi-resumable machineavailability constraints  

作　　者：CHEN Yong ZHANG An TAN Zhi-yi 

机构地区：[1]Department of Mathematics, Zhejiang University, Hangzhou 310027, China

出　　处：《Applied Mathematics(A Journal of Chinese Universities)》2011年第2期177-186,共10页高校应用数学学报（英文版）（B辑）

基　　金：Supported by the National Natural Science Foundation of China(10971191, 60021201);Fundamental Research Funds for the Central Universities(2010QNA3040);the China Postdoctoral Science Foundation

摘　　要：This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed.For the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed.For the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.

关 键 词：SCHEDULING Machine maintenance Approximation algorithm Worst-case analysis. 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O224[自动化与计算机技术—计算机科学与技术]