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


TC1 Scheduling 2
June 10, 2021  12:30 PM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.