W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Scheduling with job-splitting and fixed setup
October 26, 2012
2pm - 3pm
Many discrete optimization problems can be modeled as "scheduling" problems, where we are given a set of jobs, a set of machines, and constraints on feasible solutions, and try to find the best feasible schedule to process the jobs.
We used this scheduling framework to model practical problems in planning disaster relief operations in the Netherlands. In this talk we study the resulting scheduling problem from an algorithmic viewpoint. The particular problem we study is the following: jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time on each machine where a job part is processed. During setup a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine-, and sequence-independent.
We try to find a polynomial-time algorithm for the problem, and succeed for the special case when there are only 2 machines. We argue why the same problem with three machines is not an easy extension of the 2-machine case, leaving the complexity of this case as a tantalizing open problem. We give a constant-factor approximation algorithm for this general case with any number of machines.
This talk is (mostly) self contained; no knowledge of scheduling is assumed.
This is joint work with Rene Sitters, Suzanne van der Ster and Leen Stougie from the Vrije University in Amsterdam, Netherlands, and Anke van Zuylen from William & Mary.
We used this scheduling framework to model practical problems in planning disaster relief operations in the Netherlands. In this talk we study the resulting scheduling problem from an algorithmic viewpoint. The particular problem we study is the following: jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time on each machine where a job part is processed. During setup a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine-, and sequence-independent.
We try to find a polynomial-time algorithm for the problem, and succeed for the special case when there are only 2 machines. We argue why the same problem with three machines is not an easy extension of the 2-machine case, leaving the complexity of this case as a tantalizing open problem. We give a constant-factor approximation algorithm for this general case with any number of machines.
This talk is (mostly) self contained; no knowledge of scheduling is assumed.
This is joint work with Rene Sitters, Suzanne van der Ster and Leen Stougie from the Vrije University in Amsterdam, Netherlands, and Anke van Zuylen from William & Mary.