G. Nicosia, A. Pacifici, U. Pferschy, J. Resch, G. Righini
Given an input sequence of jobs, we consider the possibility of rescheduling the jobs to improve an objective function. However, rescheduling is limited as follows: (a) jobs can only be postponed but not preponed and (b) when a job is taken out of the sequence, it is put on a buffer of limited capacity before being reinserted in its new position closer to the end of the sequence. The buffer is organized as a stack, i.e. jobs are stored with a Last-In-First-Out policy. This situation can occur in industrial processes where parts traverse several working stations with different processing times and thus different schedules are desirable for each of them. However, rescheduling may be constrained by the technical possibilities of manipulating parts from a conveyor belt.
Four common objective functions are considered. For three of them, we construct dynamic programming algorithms running in polynomial time, while for the case of minimizing the weighted number of late jobs the problem is NP-hard. For that case we evaluate two ILP formulations. Then we develop a refined implementation of a pseudo-polynomial dynamic program and compare it to a combinatorial branch-and-bound approach.
Keywords: rescheduling, dynamic programming
Scheduled
TC1 Scheduling 2
June 10, 2021 12:30 PM
1 - GB Dantzig
