"... I have just one question to a lower bound. You mention that P|size_j,pmtn|C_{max} has a lower bound of 3/2 and give a reference to [139] by Berit Johannes. I am not sure about this.
The argument in her paper is quite short and not clear to me (page 436, line 27 ...) . She gives also a reference to one of your papers from 1994, that gives a week NP-hardness by a reduction from 2-partition (probably the one in your survey).
Or do I miss any arguments or assumptions? Is it allowed to preempt a job at non-integral points in time? Berit at least says preemptions at any point in time (page 434, line 17-19) ..."
My answer/comment
The paper of Berit Johannes is:
B.Johannes, Scheduling parallel jobs to minimize the makespan,
Journal of Scheduling, 9(5):433--452, 2006.
My paper referred to is here.
The NP-hardness proof from this paper is indeed in Theorem 5.1, page 102.
I am not convinced either, because it requires proving that there is no correct preemptive schedule shorter than 3 for P|size_j,p_j=1,pmtn|Cmax=2 if the answer to the decision version of the problem is negative.
However, here is a counter-example:
The partition instance: 5 elements of size 2. Clearly it is not possible
to divide them into 2 sets of total element size equal 5.
The corresponding scheduling instance: n=5, p_j=1, size_j=2, m=5.
A schedule of length 2.5 is shown in the figure. Tasks are denoted T1...T5, processors are denoted P1...P5.
Considering the amount of idle time introduced in the above example (=2), and the maximum number of processors able to work on the tasks when the answer to partition is negative (=m-1), I guess that the inapproximability bound should be much lower, something like 1+2/(m-1).
Berit Johannes answered: (July 2, 2011)
> I read it again, found the paragraph you are referring too, and can
> only offer the following explanation. This paper is based on my
> diploma thesis, in which I assumed that preemptions are only
> implemented at integer points in time. I admit that I failed to
> mention this in this paper, or rather, say the opposite (top of second
> page). Of course, if one can preempt at any point in time, the result
> obviously does not hold, as your example shows.
Erratum
Table 5.4, page 106, line P|size_j,pmtn|Cmax, R>3/2 should be replaced with
>=1+2/(m-1).
This page is on since June 2, 1995. Last modified :