Contributed Session Tue.1.H 3012

Tuesday, 10:30 - 12:00 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Scheduling III


Chair: Sandro Bosio



Tuesday, 11:00 - 11:25 h, Room: H 3012, Talk 2

Jens Poppenborg
Modeling the resource-constrained project scheduling problem with resource transfers using a graph approach.

Coauthor: Sigrid Knust


This presentation deals with the resource-constrained project scheduling problem (RCPSP) with resource transfers. Here, resource transfers are classified into two different categories: first- as well as second-tier resource transfers. While first-tier resource
transfers include all resource transfers where resources are directly transferred from one activity to the next, second-tier resource transfers include all resource transfers where a resource is used to transport another resource between two successive activities,
i.e. this other resource can not be transferred on its own.
The problem described here is modeled using a graph approach. For this, the activities are modeled as nodes while the resource transfers or resource flows between these activities are modeled as arcs such that an arc between two nodes corresponds to the transfer of a certain amount of units of a resource from one activity to another. Additionally, each arc is associated with the required transfer time such that schedules can be generated using longest path calculations. For this model, different neighborhood structures are introduced and some results are presented.



Tuesday, 11:30 - 11:55 h, Room: H 3012, Talk 3

Sandro Bosio
Mailroom production planning

Coauthors: David Adjiashvili, Kevin Zemmer


In a multi-feeder mailroom machine, folders (e.g., newspapers) run at high-speed through a line of independent feeders, receiving by each active feeder an advertising insert. A job is a subset of inserts to be bundled in a given number of copies, which requires a certain production time. Scheduling a job batch involves deciding the job order and, for each job, the assignment of the job inserts to the feeders.
Loading an insert on a feeder requires a given setup time, and can only be done while the feeder is idle. Given a schedule, violated setup requirements have to be resolved by stopping the machine, completing the loads, and restarting the machine. As the time needed to restart the machine dominates the setup time, minimizing the makespan is equivalent to minimizing the machine stops. Alternative objective functions are the minimization of the inserts loads (number of times each insert is loaded) and the minimization of the inserts splits (number of different feeders on which each insert is loaded). We study the complexity of the problem for each objective function, for both fixed and variable job sequence. We also consider lexicographic bi-objective optimization variants.


  payday loans online. The main active actual substance of Levitra Professional online - Vardenafil does not affect the seminal fluid and is not addictive.