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


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


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


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


  The best way to go for you to know the credible Michigan Payday Loans providers. They were lucky to produce Viagra Sublingual which dissolves under the tongue and penetrates into the blood causing erection faster than any other drugs.