Advertisement
Published in:
2009 | OriginalPaper | Chapter
Makespan Minimization with Machine Availability Constraints
Authors : Bin Fu, Yumei Huo, Hairong Zhao
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We investigate the problems of scheduling
n
jobs to
m
=
m
1
+
m
2
identical machines where
m
1
machines are always available,
m
2
machines have some specified unavailable intervals. The objective is to minimize the makespan. We assume that if a job is interrupted by the unavailable interval, it can be resumed after the machine becomes available.
We show that if at least one machine is always available, i.e.
m
1
> 0, then the PTAS for Multiple Subset Sum problem given by Kellerer [3] can be applied to get a PTAS; otherwise,
m
=
m
2
, every machine has some unavailable intervals, we show that if (
m
− 1) machines each of which has unavailable intervals with total length bounded by
α
(
n
) ·
P
sum
/
m
where
P
sum
is the total processing time of all jobs and
α
(
n
) can be any non-negative function, we can develop a (1 +
α
(
n
) +
ε
) −approximation algorithm for any constant 0 <
ε
< 1; finally we show that there does not exist any polynomial time (1 +
α
(
n
) −
o
(1)) −approximation unless P=NP.