## Contributed Session Mon.2.H 3012

#### Monday, 13:15 - 14:45 h, Room: H 3012

**Cluster 2: Combinatorial optimization** [...]

### Scheduling I

**Chair: George Steiner**

**Monday, 13:15 - 13:40 h, Room: H 3012, Talk 1**

**Thomas Rieger**

Two variants of flexible job shop scheduling with blockages

**Coauthors: Ronny Hansmann, Uwe T. Zimmermann**

**Abstract:**

Motivated by an application in rail car maintenance, we discuss makespan-minimization for two variants of flexible job shop scheduling with work centers (FJc). In contrast to standard FJc in these variants a work center (rail track) consists of a linearly ordered set of machines with restricted accessibility. In particular, a busy machine blocks both the access to and the exit from all succeeding machines of a work center. The two considered variants only differ in the implication of the latter restricting requirement. If a succeeding machine is blocked when it completes a job then this job is either allowed to wait on its machine (until the exit is free again) or not.

In particular, we present the computational complexity and solution methods (heuristical and exact) and introduce a mixed integer linear programming model for both variants.

Our exact methods are based on a dedicated branch-and-bound-implementation using bounds generated from certain longest paths.

Finally, we present some computational results for several data sets, discuss the solution quality of both FJc-variants and

compare our results to results obtained using the commercial solvers CPLEX and Gurobi.

**Monday, 13:45 - 14:10 h, Room: H 3012, Talk 2**

**Leen Stougie**

Scheduling with job-splitting and fixed setup

**Coauthors: Frans Schalenkamp, RenĂ© Sitters, Suzanne van der Ster, Anke Zuylen, van**

**Abstract:**

We consider a scheduling problem with a *a fixed setup time* and *job-splitting*. Jobs can be preempted and machines can work on the same job simultaneously. We encountered this problem in studying disaster relief operations. We consider minimisation of total completion time. The version with preemption and fixed setup time *s* is still solved by the Shortest Processing Time first rule (SPT), in which the option of preemption is not used. The situation with job-splitting is much less clear. If *s* is very large, then splitting becomes too expensive and the problem is solved by SPT again. If *s* is very small (say 0), then each job is split over all machines and the jobs are scheduled in SPT order. To find out where to start splitting jobs and over how many machines appears to be a non-trivial problem.

We will present a polynomial time algorithm for the case in which there are 2 machines exploiting the structure of optimal solutions. Some of the crucial properties of optimal solutions already fail to hold on 3 machines. This leaves the complexity of the problem for more than 2 machines open.

**Monday, 14:15 - 14:40 h, Room: H 3012, Talk 3**

**George Steiner**

Scheduling and the traveling salesman problem on permuted monge matrices

**Abstract:**

A large variety of scheduling problems has been shown to be solvable as

special cases of the Traveling Salesman Problem (TSP) on permuted Monge

matrices. Although the TSP on permuted Monge matrices is known to be strongly

NP-hard, polynomial-time solutions exist for many of the special cases

generated by the scheduling problems. Furthermore, a simple subtour-patching

heuristic is asymptotically optimal for the TSP on permuted Monge matrices

under some mild technical conditions