Open-shop scheduling
In theoretical computer science and operations research, the open-shop scheduling problem (OSSP) is a scheduling problem in which a given set of jobs must each be processed for given amounts of time at each of a given set of workstations, in an arbitrary order, and the goal is to determine the time at which each job is to be processed at each workstation. The problem was first studied by Teofilo F. Gonzalez and Sartaj Sahni in 1976.[1]
Definition
More precisely, the input to the open-shop scheduling problem consists of a set of n jobs, another set of m workstations, and a two-dimensional table of the amount of time each job should spend at each workstation (possibly zero). Each job may be processed only at one workstation at a time, and each workstation can process only one job at a time. However, unlike the job-shop problem, the order in which the processing steps happen can vary freely. The goal is to assign a time for each job to be processed by each workstation, so that no two jobs are assigned to the same workstation at the same time, no job is assigned to two workstations at the same time, and every job is assigned to each workstation for the desired amount of time. The usual measure of quality of a solution is its makespan, the amount of time from the start of the schedule (the first assignment of a job to a workstation) to its end (the finishing time of the last job at the last workstation).
Computational complexity
The open-shop scheduling problem can be solved in polynomial time for instances that have only two workstations or only two jobs. It may also be solved in polynomial time when all nonzero processing times are equal: in this case the problem becomes equivalent to edge coloring a bipartite graph that has the jobs and workstations as its vertices, and that has an edge for every job-workstation pair that has a nonzero processing time. The color of an edge in the coloring corresponds to the segment of time at which a job-workstation pair is scheduled to be processed. Because the line graphs of bipartite graphs are perfect graphs, bipartite graphs may be edge-colored in polynomial time.
For three or more workstations, or three or more jobs, with varying processing times, open-shop scheduling is NP-hard.
See also
References
- ^ Gonzalez, Teofilo; Sahni, Sartaj (1976), "Open shop scheduling to minimize finish time", Journal of the ACM, 23 (4): 665–679, CiteSeerX 10.1.1.394.1507, doi:10.1145/321978.321985, MR 0429089.
- Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B. (1997), "Short shop schedules", Operations Research, 45 (2): 288–294, doi:10.1287/opre.45.2.288, JSTOR 171745, MR 1644998.