357:. In the graph drawing applications of the Coffman–Graham algorithm, the resulting directed acyclic graph may not be the same as the graph being drawn, and in the scheduling applications it may not have an edge for every precedence constraint of the input: in both cases, the transitive reduction removes redundant edges that are not necessary for defining the partial order.
436:; that is, for scheduling problems with unit length jobs on two processors, or for layered graph drawing problems with at most two vertices per layer. A closely related algorithm also finds the optimal solution for scheduling of jobs with varying lengths, allowing pre-emption of scheduled jobs, on two processors. For
264:-coordinate), which is the problem solved by the Coffman–Graham algorithm. Although there exist alternative approaches than the Coffman–Graham algorithm to the layering step, these alternatives in general are either not able to incorporate a bound on the maximum width of a level or rely on complex
176:
of the assignment (the time from the beginning of the first job until the completion of the final job). Abstractly, the precedence constraints define a partial order on the jobs, so the problem can be rephrased as one of assigning the elements of this partial order to levels (time slots) in such a
69:
is the number of jobs that can be scheduled at any one time, and the partial order describes prerequisite relations between the jobs. The goal is to find a schedule that completes all jobs in minimum total time. Subsequently, the same algorithm has also been used in
31:
into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound
480:
of two-processor schedules, the sum of the completion times of the individual jobs. A related algorithm can be used to minimize the total flow time for a version of the problem in which preemption of jobs is allowed.
388:. If two vertices have the same most recently added incoming neighbor, the algorithm breaks the tie in favor of the one whose second most recently added incoming neighbor is earlier, etc.
465:, or belongs to several related classes of partial orders, the Coffman–Graham algorithm finds a solution with the minimum number of levels regardless of its width bound.
181:
elements per level), respecting the precedence constraints. This application was the original motivation for
Coffman and Graham to develop their algorithm.
721:. Bastert and Matuszewski also include a description of the Coffman–Graham algorithm; however, they omit the transitive reduction stage of the algorithm.
468:
As well as finding schedules with small makespan, the
Coffman–Graham algorithm (modified from the presentation here so that it topologically orders the
477:
226:
Dummy vertices are introduced within each edge so that the subdivided edges all connect pairs of vertices that are in adjacent levels of the drawing.
223:-coordinate. In this way, all edges of the directed acyclic graph and most edges of the original graph will be oriented consistently downwards.
372:
by the set of positions of their incoming neighbors. To do so, add the vertices one at a time to the ordering, at each step choosing a vertex
271:
More abstractly, both of these problems can be formalized as a problem in which the input consists of a partially ordered set and an integer
215:-coordinates in such a way that, for each edge, the starting vertex of the edge has a higher coordinate than the ending vertex, with at most
168:
begins. Each job is assumed to take unit time to complete. The scheduling task is to assign each of these jobs to time slots on a system of
297:
elements are assigned the same number as each other, and minimizing the difference between the smallest and the largest assigned numbers.
511:. However, this analysis omits the time for constructing the transitive reduction, which is not known to be possible within this bound.
636:
1122:
733:
885:
Chardon, Marc; Moukrim, Aziz (2005), "The
Coffman-Graham algorithm optimally solves UET task systems with overinterval orders",
634:
Sugiyama, Kozo; Tagawa, Shôjirô; Toda, Mitsuhiko (1981), "Methods for visual understanding of hierarchical system structures",
618:
887:
443:, the Coffman–Graham algorithm uses a number of levels (or computes a schedule with a makespan) that is within a factor of
275:. The desired output is an assignment of integer level numbers to the elements of the partially ordered set such that, if
256:-coordinate assignment again involves grouping elements of a partially ordered set (the vertices of the graph, with the
105:
In the version of the job shop scheduling problem solved by the
Coffman–Graham algorithm, one is given a set of
772:
238:
384:
is earlier than the most recently added incoming neighbor of any other vertex that could be added in place of
734:
Graph
Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers
1127:
524:
380:
are all already part of the partial ordering, and such that the most recently added incoming neighbor of
523:. Sethi also shows how to implement the level assignment stage of the algorithm efficiently by using a
395:
to levels in the reverse of the topological ordering constructed in the previous step. For each vertex
704:
Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in
Kaufmann, Michael;
850:
813:
1117:
922:
767:
550:
403:
to a level that is at least one step higher than the highest level of any outgoing neighbor of
205:
54:
848:
Braschi, Bertrand; Trystram, Denis (1994), "A new insight into the
Coffman–Graham algorithm",
558:
974:
185:
28:
476:
and places the vertices as early as possible rather than as late as possible) minimizes the
1098:
1054:
1016:
948:
925:; Sethuraman, J.; Timkovsky, V. G. (2003), "Ideal preemptive schedules on two processors",
908:
871:
834:
752:
653:
587:
520:
461:
times as many levels as is optimal. When the partial order of precedence constraints is an
310:
90:
82:
78:
into layers of fixed widths so that most or all edges are directed consistently downwards.
8:
411:
elements assigned to it, and that is as low as possible subject to these two constraints.
369:
361:
265:
62:
43:, it uses the minimum possible number of distinct levels, and in general it uses at most
1004:
952:
789:
712:, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120,
657:
591:
737:, Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, pp. 16–30,
1089:
970:
793:
614:
314:
731:
Healy, Patrick; Nikolov, Nikola S. (2002), "How to layer a directed acyclic graph",
595:
285:
is an ordered pair of related elements of the partial order, the number assigned to
248:
The vertices and edges of the graph are drawn with the coordinates assigned to them.
204:
is chosen, and the edges of this set reversed, in order to convert the input into a
1084:
1042:
994:
986:
956:
936:
927:
896:
859:
822:
781:
738:
713:
685:
661:
641:
575:
566:
201:
93:
data structure as a subroutine. If the transitive reduction is not given, it takes
1094:
1068:
1050:
1012:
944:
904:
867:
830:
748:
705:
649:
583:
94:
462:
193:
75:
999:
940:
900:
863:
645:
1111:
1072:
554:
469:
71:
58:
1075:(1985), "A linear-time algorithm for a special case of disjoint set union",
785:
743:
717:
257:
515:
shows how to implement the topological ordering stage of the algorithm in
990:
681:
516:
234:
86:
688:; Tollis, Ioannis G. (1999), "Chapter 9: Layered drawings of digraphs",
260:
ordering on the vertex set) into layers (sets of vertices with the same
177:
way that each time slot has at most as many jobs as processors (at most
85:(covering relation), the Coffman–Graham algorithm can be implemented in
1030:
808:
579:
1008:
429:
originally proved, their algorithm computes an optimal assignment for
65:. In this application, the elements to be ordered are jobs, the bound
527:. In particular, with a version of this structure published later by
24:
1046:
826:
611:
Handbook of
Scheduling: Algorithms, Models, and Performance Analysis
173:
770:(1969), "Optimal preemptive scheduling on two-processor systems",
977:(1978), "Complexity of scheduling under precedence constraints",
496:
state the time complexity of the
Coffman–Graham algorithm, on an
609:
Leung, Joseph Y.-T. (2004), "Some basic scheduling algorithms",
679:
196:, and a drawing of a graph is constructed in several stages:
811:(1977), "Worst case analysis of two scheduling algorithms",
305:
The
Coffman–Graham algorithm performs the following steps.
921:
690:
Graph Drawing: Algorithms for the Visualization of Graphs
241:
in the resulting drawing, and the vertices are assigned
100:
134:, together with a system of precedence constraints
969:
703:
637:IEEE Transactions on Systems, Man, and Cybernetics
633:
493:
189:
16:Method for partitioning partial orders into levels
61:, who published it in 1972 for an application in
1109:
245:-coordinates consistently with this permutation.
1033:(1976), "Scheduling graphs on two processors",
847:
884:
559:"Optimal scheduling for two-processor systems"
549:
489:
426:
765:
730:
229:Within each group of vertices with the same
211:The vertices of the graph are given integer
1067:
528:
376:to add such that the incoming neighbors of
339:and there does not exist any third element
1088:
998:
742:
806:
74:, as a way of placing the vertices of a
1077:Journal of Computer and System Sciences
289:is smaller than the number assigned to
1110:
675:
673:
671:
545:
543:
208:with (if possible) few reversed edges.
1029:
608:
531:, this stage also takes linear time.
512:
172:identical processors, minimizing the
888:SIAM Journal on Discrete Mathematics
81:For a partial ordering given by its
841:
800:
668:
540:
309:Represent the partial order by its
50:times as many levels as necessary.
13:
710:Drawing Graphs: Methods and Models
484:
457:, this means that it uses at most
368:in which the vertices are ordered
190:Sugiyama, Tagawa & Toda (1981)
101:Problem statement and applications
14:
1139:
692:, Prentice Hall, pp. 265–302
420:
494:Lenstra & Rinnooy Kan (1978)
300:
27:for arranging the elements of a
1123:Processor scheduling algorithms
1061:
1023:
963:
915:
878:
343:of the partial order for which
773:IEEE Transactions on Computers
759:
724:
697:
627:
602:
500:-element partial order, to be
450:of optimal. For instance, for
233:-coordinate, the vertices are
1:
534:
407:, that does not already have
1090:10.1016/0022-0000(85)90014-5
7:
525:disjoint-set data structure
490:Coffman & Graham (1972)
427:Coffman & Graham (1972)
415:
317:, a directed acyclic graph
10:
1144:
219:vertices sharing the same
1035:SIAM Journal on Computing
941:10.1007/s00236-003-0119-6
901:10.1137/S0895480101394999
864:10.1137/S0097539790181889
851:SIAM Journal on Computing
814:SIAM Journal on Computing
646:10.1109/TSMC.1981.4308636
529:Gabow & Tarjan (1985)
237:in order to minimize the
159:be completed before job
21:Coffman–Graham algorithm
786:10.1109/T-C.1969.222573
744:10.1007/3-540-45848-4_2
718:10.1007/3-540-44969-8_5
680:di Battista, Giuseppe;
640:, SMC-11 (2): 109–125,
519:, based on the idea of
391:Assign the vertices of
252:In this framework, the
321:that has an edge from
206:directed acyclic graph
188:framework outlined by
55:Edward G. Coffman, Jr.
975:Rinnooy Kan, A. H. G.
186:layered graph drawing
29:partially ordered set
1073:Tarjan, Robert Endre
991:10.1287/opre.26.1.22
521:partition refinement
362:topological ordering
311:transitive reduction
293:, such that at most
91:partition refinement
83:transitive reduction
979:Operations Research
266:integer programming
239:number of crossings
150:requiring that job
63:job shop scheduling
1128:Optimal scheduling
1000:10338.dmlcz/141477
923:Coffman, E. G. Jr.
580:10.1007/bf00288685
551:Coffman, E. G. Jr.
53:It is named after
780:(11): 1014–1020,
686:Tamassia, Roberto
620:978-1-58488-397-5
370:lexicographically
315:covering relation
97:to construct it.
1135:
1103:
1101:
1092:
1069:Gabow, Harold N.
1065:
1059:
1057:
1027:
1021:
1019:
1002:
967:
961:
959:
928:Acta Informatica
919:
913:
911:
882:
876:
874:
845:
839:
837:
804:
798:
796:
763:
757:
755:
746:
728:
722:
720:
706:Wagner, Dorothea
701:
695:
693:
677:
666:
664:
631:
625:
623:
606:
600:
598:
567:Acta Informatica
563:
547:
510:
499:
475:
460:
456:
449:
442:
435:
410:
406:
402:
398:
394:
387:
383:
379:
375:
367:
356:
342:
338:
320:
296:
292:
288:
284:
274:
263:
255:
244:
232:
222:
218:
214:
202:feedback arc set
180:
171:
167:
158:
149:
133:
108:
68:
49:
42:
35:
1143:
1142:
1138:
1137:
1136:
1134:
1133:
1132:
1108:
1107:
1106:
1066:
1062:
1047:10.1137/0205005
1028:
1024:
968:
964:
920:
916:
883:
879:
846:
842:
827:10.1137/0206037
805:
801:
764:
760:
729:
725:
702:
698:
678:
669:
632:
628:
621:
607:
603:
561:
548:
541:
537:
501:
497:
487:
485:Time complexity
478:total flow time
473:
458:
451:
444:
437:
430:
423:
418:
408:
404:
400:
396:
392:
385:
381:
377:
373:
365:
344:
340:
330:
318:
303:
294:
290:
286:
276:
272:
261:
253:
242:
230:
220:
216:
212:
192:the input is a
178:
169:
165:
160:
156:
151:
147:
140:
135:
132:
123:
116:
110:
106:
103:
95:polynomial time
66:
44:
37:
33:
17:
12:
11:
5:
1141:
1131:
1130:
1125:
1120:
1105:
1104:
1083:(2): 209–221,
1060:
1022:
971:Lenstra, J. K.
962:
935:(8): 597–612,
914:
895:(1): 109–121,
877:
858:(3): 662–669,
840:
821:(3): 518–536,
799:
768:Coffman, E. G.
766:Muntz, R. R.;
758:
723:
696:
667:
626:
619:
601:
574:(3): 200–213,
538:
536:
533:
486:
483:
463:interval order
422:
421:Output quality
419:
417:
414:
413:
412:
389:
358:
302:
299:
250:
249:
246:
227:
224:
209:
194:directed graph
163:
154:
145:
138:
128:
121:
114:
102:
99:
76:directed graph
15:
9:
6:
4:
3:
2:
1140:
1129:
1126:
1124:
1121:
1119:
1118:Graph drawing
1116:
1115:
1113:
1100:
1096:
1091:
1086:
1082:
1078:
1074:
1070:
1064:
1056:
1052:
1048:
1044:
1040:
1036:
1032:
1026:
1018:
1014:
1010:
1006:
1001:
996:
992:
988:
984:
980:
976:
972:
966:
958:
954:
950:
946:
942:
938:
934:
930:
929:
924:
918:
910:
906:
902:
898:
894:
890:
889:
881:
873:
869:
865:
861:
857:
853:
852:
844:
836:
832:
828:
824:
820:
816:
815:
810:
803:
795:
791:
787:
783:
779:
775:
774:
769:
762:
754:
750:
745:
740:
736:
735:
727:
719:
715:
711:
707:
700:
691:
687:
683:
676:
674:
672:
663:
659:
655:
651:
647:
643:
639:
638:
630:
622:
616:
613:, CRC Press,
612:
605:
597:
593:
589:
585:
581:
577:
573:
569:
568:
560:
556:
555:Graham, R. L.
552:
546:
544:
539:
532:
530:
526:
522:
518:
514:
508:
504:
495:
491:
482:
479:
471:
470:reverse graph
466:
464:
454:
448:
440:
433:
428:
390:
371:
363:
359:
355:
351:
347:
337:
333:
328:
324:
316:
312:
308:
307:
306:
301:The algorithm
298:
283:
279:
269:
267:
259:
247:
240:
236:
228:
225:
210:
207:
203:
199:
198:
197:
195:
191:
187:
182:
175:
166:
157:
148:
141:
131:
127:
120:
113:
98:
96:
92:
88:
84:
79:
77:
73:
72:graph drawing
64:
60:
59:Ronald Graham
56:
51:
48:
40:
30:
26:
22:
1080:
1076:
1063:
1041:(1): 73–82,
1038:
1034:
1025:
985:(1): 22–35,
982:
978:
965:
932:
926:
917:
892:
886:
880:
855:
849:
843:
818:
812:
802:
777:
771:
761:
732:
726:
709:
699:
689:
682:Eades, Peter
635:
629:
610:
604:
571:
565:
513:Sethi (1976)
506:
502:
488:
467:
452:
446:
445:2 − 2/
438:
431:
424:
360:Construct a
353:
349:
345:
335:
331:
326:
322:
304:
281:
277:
270:
268:procedures.
258:reachability
251:
183:
161:
152:
143:
136:
129:
125:
118:
111:
104:
80:
52:
46:
45:2 − 2/
38:
20:
18:
1031:Sethi, Ravi
809:Sethi, Ravi
807:Lam, Shui;
517:linear time
87:linear time
1112:Categories
535:References
89:using the
794:206617438
329:whenever
25:algorithm
708:(eds.),
596:40603807
557:(1972),
416:Analysis
235:permuted
174:makespan
1099:0801823
1055:0398156
1017:0462553
957:7016804
949:1996238
909:2178187
872:1274650
835:0496614
753:1962416
662:8367756
654:0611436
588:0334913
184:In the
124:, ...,
36:. When
1097:
1053:
1015:
1009:169889
1007:
955:
947:
907:
870:
833:
792:
751:
660:
652:
617:
594:
586:
441:> 2
399:, add
23:is an
1005:JSTOR
953:S2CID
790:S2CID
658:S2CID
592:S2CID
562:(PDF)
352:<
348:<
334:<
280:<
142:<
109:jobs
615:ISBN
492:and
57:and
19:The
1085:doi
1043:doi
995:hdl
987:doi
937:doi
897:doi
860:doi
823:doi
782:doi
739:doi
714:doi
642:doi
576:doi
472:of
459:4/3
455:= 3
434:= 2
425:As
364:of
325:to
313:or
41:= 2
1114::
1095:MR
1093:,
1081:30
1079:,
1071:;
1051:MR
1049:,
1037:,
1013:MR
1011:,
1003:,
993:,
983:26
981:,
973:;
951:,
945:MR
943:,
933:39
931:,
905:MR
903:,
893:19
891:,
868:MR
866:,
856:23
854:,
831:MR
829:,
817:,
788:,
778:18
776:,
749:MR
747:,
684:;
670:^
656:,
650:MR
648:,
590:,
584:MR
582:,
570:,
564:,
553:;
542:^
200:A
117:,
1102:.
1087::
1058:.
1045::
1039:5
1020:.
997::
989::
960:.
939::
912:.
899::
875:.
862::
838:.
825::
819:6
797:.
784::
756:.
741::
716::
694:.
665:.
644::
624:.
599:.
578::
572:1
509:)
507:n
505:(
503:O
498:n
474:G
453:W
447:W
439:W
432:W
409:W
405:v
401:v
397:v
393:G
386:v
382:v
378:v
374:v
366:G
354:y
350:z
346:x
341:z
336:y
332:x
327:y
323:x
319:G
295:W
291:y
287:x
282:y
278:x
273:W
262:y
254:y
243:x
231:y
221:y
217:W
213:y
179:W
170:W
164:j
162:J
155:i
153:J
146:j
144:J
139:i
137:J
130:n
126:J
122:2
119:J
115:1
112:J
107:n
67:W
47:W
39:W
34:W
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.