Scheduling a single machine with compressible jobs to minimize maximum lateness
share
The problem of scheduling non-simultaneously released jobs with due dates on a single machine with the objective to minimize the maximum job lateness is known to be strongly NP-hard. Here we consider an extended model in which the compression of the job processing times is allowed. The compression is accomplished at the cost of involving additional emerging resources, whose use, however, yields some cost. With a given upper limit U on the total allowable cost, one wishes to minimize the maximum job lateness. This setting is realistic in practice because by completing some emerging jobs earlier using some available resources, the objective function value might be decreased. In particular, for minimizing the maximum job lateness, shortening the processing time of specific jobs turns out to be very helpful. Although the generalized problem remains strongly NP-hard and is considerably more complicated than the generic non-compressible version, given a "sufficient amount" of additional resources, it might be possible to solve the problem optimally. In particular, we establish the compression rate for some specific jobs and develop an algorithm that obtains an optimal solution for the processing times reduced in this way. Such an approach has an obvious benefit in practice since the manufacturer can be provided with an information about the required amount of additional resources in order to solve the problem optimally.
READ FULL TEXT