EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3099. Polynomial-time algorithms for solving timing problems in single-machine rescheduling
Invited abstract in session WD-60: Flow shop and single machine scheduling , stream Project Management and Scheduling.
Wednesday, 14:30-16:00Room: S09 (building: 101)
Authors (first author is the speaker)
| 1. | Elena Rener
|
| University of Bern | |
| 2. | Fabio Salassa
|
| DAUIN, Politecnico di Torino | |
| 3. | Vincent T'KINDT
|
| University of Tours |
Abstract
Rescheduling problems are understood as strategies for updating existing schedules to deal with unexpected changes in the available data. When the change is given by the arrival of a new set of jobs, which are unknown at the time of scheduling, we speak of rescheduling for new orders.
In these problems, we consider two sets of jobs, a set of old jobs and a set of new jobs, that must be scheduled together on a single machine. For the set of old jobs, we know the original completion times, that is, the times based on the schedule prior to the insertion of the new jobs. According to these times, additional activities may have been planned and resources made available. Thus, the goal of rescheduling is twofold: to minimize some classical objective function over all jobs, and to minimize the disruption of the original schedule.
When the disruption is measured as the total absolute time deviation from the original completion times, the search for optimal solutions raises the problem of determining the insertion of idle time. We provide timing algorithms for solving this problem when the sequence of jobs is known. We show that the proposed algorithms devise the efficient frontier of solutions in polynomial time, and compute an optimal solution in polynomial time, if a disruption threshold is given.
Keywords
- Scheduling
Status: accepted
Back to the list of papers