208:, 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
232:
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
203:
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
224:
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
212:, 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).
185:
157:
426:
419:
266:
is a similar problem but with a yet additional constraint – the operations must be done in a specific order.
76:- the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as
465:
455:
187:" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.
412:
574:
460:
450:
481:
248:
For three or more workstations, or three or more jobs, with varying processing times, open-shop scheduling is
553:
527:
517:
435:
311:
120:
40:
522:
491:
270:
28:
316:
548:
496:
355:
262:
109:
36:
532:
383:
337:
302:
163:
359:
375:
321:
205:
132:
32:
395:
333:
391:
329:
238:
229:
221:
568:
242:
225:
363:
341:
297:
113:
404:
278:
constraint – each operation must be done on a specific machine.
234:
379:
325:
512:
209:
73:
249:
387:
72:
machines with varying processing power, while trying to minimize the
195:
The input to the open-shop scheduling problem consists of a set of
408:
245:, bipartite graphs may be edge-colored in polynomial time.
68:
of varying processing times, which need to be scheduled on
127:
in the first field. For example, the problem denoted by "
300:(1976), "Open shop scheduling to minimize finish time",
121:
three-field notation for optimal job-scheduling problems
166:
135:
358:; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.;
43:. In a general job-scheduling problem, we are given
541:
505:
474:
443:
220:The open-shop scheduling problem can be solved in
179:
151:
274:is a job-shop scheduling but with an additional
172:
420:
8:
427:
413:
405:
315:
171:
165:
140:
134:
108:order. The problem was first studied by
288:
123:, the open-shop variant is denoted by
7:
14:
104:which need to be processed in an
366:(1997), "Short shop schedules",
80:, each job consists of a set of
1:
21:open-shop scheduling problem
591:
180:{\displaystyle C_{\max }}
216:Computational complexity
554:Truthful job scheduling
506:Optimization objectives
362:; Sevast'janov, S. V.;
436:Optimal job scheduling
181:
153:
152:{\displaystyle p_{ij}}
41:optimal job scheduling
380:10.1287/opre.45.2.288
326:10.1145/321978.321985
199:jobs, another set of
182:
154:
39:. It is a variant of
271:Flow-shop scheduling
164:
133:
78:open-shop scheduling
29:optimization problem
17:Open-shop scheduling
549:Interval scheduling
368:Operations Research
296:Gonzalez, Teofilo;
263:Job-shop scheduling
110:Teofilo F. Gonzalez
37:operations research
575:Optimal scheduling
542:Other requirements
466:Unrelated machines
456:Identical machines
303:Journal of the ACM
177:
149:
562:
561:
356:Williamson, D. P.
97:, ...,
61:, ...,
582:
475:Multi-stage jobs
461:Uniform machines
429:
422:
415:
406:
399:
398:
352:
346:
344:
319:
293:
256:Related problems
239:bipartite graphs
206:job-shop problem
186:
184:
183:
178:
176:
175:
158:
156:
155:
150:
148:
147:
119:In the standard
33:computer science
590:
589:
585:
584:
583:
581:
580:
579:
565:
564:
563:
558:
537:
501:
470:
439:
433:
403:
402:
354:
353:
349:
317:10.1.1.394.1507
295:
294:
290:
285:
258:
230:bipartite graph
222:polynomial time
218:
193:
167:
162:
161:
136:
131:
130:
102:
96:
89:
66:
60:
53:
12:
11:
5:
588:
586:
578:
577:
567:
566:
560:
559:
557:
556:
551:
545:
543:
539:
538:
536:
535:
530:
525:
520:
515:
509:
507:
503:
502:
500:
499:
494:
489:
484:
482:Parallel tasks
478:
476:
472:
471:
469:
468:
463:
458:
453:
451:Single machine
447:
445:
444:One-stage jobs
441:
440:
434:
432:
431:
424:
417:
409:
401:
400:
374:(2): 288–294,
360:Lenstra, J. K.
347:
310:(4): 665–679,
287:
286:
284:
281:
280:
279:
267:
257:
254:
243:perfect graphs
217:
214:
192:
189:
174:
170:
146:
143:
139:
100:
94:
87:
64:
58:
51:
13:
10:
9:
6:
4:
3:
2:
587:
576:
573:
572:
570:
555:
552:
550:
547:
546:
544:
540:
534:
531:
529:
526:
524:
521:
519:
516:
514:
511:
510:
508:
504:
498:
495:
493:
490:
488:
485:
483:
480:
479:
477:
473:
467:
464:
462:
459:
457:
454:
452:
449:
448:
446:
442:
437:
430:
425:
423:
418:
416:
411:
410:
407:
397:
393:
389:
385:
381:
377:
373:
369:
365:
364:Shmoys, D. B.
361:
357:
351:
348:
343:
339:
335:
331:
327:
323:
318:
313:
309:
305:
304:
299:
298:Sahni, Sartaj
292:
289:
282:
277:
273:
272:
268:
265:
264:
260:
259:
255:
253:
251:
246:
244:
240:
236:
231:
227:
226:edge coloring
223:
215:
213:
211:
207:
202:
198:
190:
188:
168:
160:
144:
141:
137:
126:
122:
117:
115:
111:
107:
103:
93:
86:
83:
79:
75:
71:
67:
57:
50:
46:
42:
38:
34:
30:
26:
22:
18:
486:
371:
367:
350:
307:
301:
291:
275:
269:
261:
247:
219:
200:
196:
194:
128:
124:
118:
114:Sartaj Sahni
105:
98:
91:
84:
81:
77:
69:
62:
55:
48:
44:
24:
20:
16:
15:
235:line graphs
533:Throughput
283:References
191:Definition
82:operations
528:Tardiness
518:Earliness
492:Flow shop
487:Open shop
312:CiteSeerX
116:in 1976.
106:arbitrary
569:Category
523:Lateness
513:Makespan
497:Job shop
438:problems
210:makespan
74:makespan
27:) is an
396:1644998
342:1642775
334:0429089
250:NP-hard
90:,
54:,
394:
388:171745
386:
340:
332:
314:
384:JSTOR
338:S2CID
47:jobs
276:flow
241:are
112:and
35:and
25:OSSP
376:doi
322:doi
237:of
173:max
129:O3|
31:in
19:or
571::
392:MR
390:,
382:,
372:45
370:,
336:,
330:MR
328:,
320:,
308:23
306:,
252:.
228:a
428:e
421:t
414:v
378::
345:.
324::
201:m
197:n
169:C
159:|
145:j
142:i
138:p
125:O
101:n
99:O
95:2
92:O
88:1
85:O
70:m
65:n
63:J
59:2
56:J
52:1
49:J
45:n
23:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.