1624:-competitive. In 1992, Bartal, Fiat, Karloff and Vohra presented an algorithm that is 1.986 competitive. A 1.945-competitive algorithm was presented by Karger, Philips and Torng in 1994. In 1992, Albers provided a different algorithm that is 1.923-competitive. Currently, the best known result is an algorithm given by Fleischer and Wahl, which achieves a competitive ratio of 1.9201.
1810:
the optimal makespan of a JSP instance without actually producing the optimal schedule. Preliminary results show an accuracy of around 80% when supervised machine learning methods were applied to classify small randomly generated JSP instances based on their optimal scheduling efficiency compared to
1660:
The simplest form of the offline makespan minimisation problem deals with atomic jobs, that is, jobs that are not subdivided into multiple operations. It is equivalent to packing a number of items of various different sizes into a fixed number of bins, such that the maximum bin size needed is as
1687:
The basic form of the problem of scheduling jobs with multiple (M) operations, over M machines, such that all of the first operations must be done on the first machine, all of the second operations on the second, etc., and a single job cannot be performed in parallel, is known as the
1474:
is the number of machines. Notice that with the above definition, scheduling efficiency is simply the makespan normalized to the number of machines and the total processing time. This makes it possible to compare the usage of resources across JSP instances of different size.
2636:
Jacek Błażewicz, Erwin Pesch, Małgorzata Sterna, The disjunctive graph machine representation of the job shop scheduling problem, European
Journal of Operational Research, Volume 127, Issue 2, 1 December 2000, Pages 317-331, ISSN 0377-2217,
1431:
733:
1787:/2 machines into an (imaginary) Machining center, MC1, and the remaining Machines into a Machining Center MC2. Then the total processing time for a Job P on MC1 = sum( operation times on first
1710:
A heuristic algorithm by S. M. Johnson can be used to solve the case of a 2 machine N job problem when all jobs are to be processed in the same order. The steps of algorithm are as follows:
959:
875:
820:
552:
447:
376:
1518:
1281:
1563:
215:
1079:
1016:
1235:
1174:
1137:
1108:
904:
765:
659:
582:
516:
483:
1205:
630:
1590:
608:
1776:
Johnson's method only works optimally for two machines. However, since it is optimal, and easy to compute, some researchers have tried to adopt it for M machines, (
1460:
1296:
3181:
1661:
small as possible. (If instead the number of bins is to be minimised, and the bin size is fixed, the problem becomes a different problem, known as the
1627:
A lower bound of 1.852 was presented by Albers. Taillard instances has an important role in developing job-shop scheduling with makespan objective.
143:
1612:-competitive, where m is the number of machines. Also, it was proved that List scheduling is optimum online algorithm for 2 and 3 machines. The
289:
is clearly also NP-hard since the TSP is a special case of the JSP with a single job (the cities are the machines and the salesman is the job).
667:
3154:
2866:
2612:
1798:
By doing so, we have reduced the m-Machine problem into a Two
Machining center scheduling problem. We can solve this using Johnson's method.
1679:
in 1987 that finds an approximate solution to the offline makespan minimisation problem with atomic jobs to any desired degree of accuracy.
2479:
is a similar problem but without the constraint that each operation must be done on a specific machine (only the order constraint is kept).
1676:
1291:
Scheduling efficiency can be defined for a schedule through the ratio of total machine idle time to the total processing time as below:
2592:
Maccarthy (1993). "Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling".
229:
Machines can have duplicates (flexible job shop with duplicate machines) or belong to groups of identical machines (flexible job shop).
2926:
554:
denote the set of all sequential assignments of jobs to machines, such that every job is done by every machine exactly once; elements
3174:
2521:
1483:
One of the first problems that must be dealt with in the JSP is that many proposed solutions have infinite cost: i.e., there exists
3138:
3120:
S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.
1641:
In 2011 Xin Chen et al. provided optimal algorithms for online scheduling on two related machines improving previous results.
146:
was presented, by Graham in 1966. The best problem instances for a basic model with a makespan objective are due to
Taillard.
123:
that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the
1634:
for m>2, that is, no optimal solution can be computed in deterministic polynomial time for three or more machines (unless
87:– the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as
3334:
3220:
3210:
217:" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.
2578:
1613:
3167:
2627:
B. Roy, B. Sussmann, Les problèmes d’ordonnancement avec constraintes disjonctives, SEMA, Note D.S., No. 9, Paris, 1964.
2511:
2506:
3329:
3215:
1783:
The idea is as follows: Imagine that each job requires m operations in sequence, on M1, M2 … Mm. We combine the first
1593:
909:
825:
770:
1018:. The cost function may be interpreted as a "total processing time", and may have some expression in terms of times
528:
381:
310:
1486:
278:
139:
3205:
2887:
2747:
1655:
1240:
3236:
286:
1523:
3308:
3094:
Proceedings of the 9th
Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence
160:
3282:
3272:
3190:
3101:
3056:
2896:
1021:
970:
150:
138:, but the theme has wide applications beyond that type of instance. This problem is one of the best known
51:
3092:
Khuri, Sami; Miryala, Sowmya Rao (1999). "Genetic
Algorithms for Solving Open Shop Scheduling Problems".
1210:
1149:
1113:
1084:
880:
741:
635:
557:
492:
459:
3277:
3146:
2684:
1179:
2924:
Garey, M. R.; Johnson, D. S.; Sethi, Ravi (1976). "The
Complexity of Flowshop and Jobshop Scheduling".
2782:
Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). "New
Algorithms for an Ancient Scheduling Problem".
3246:
3241:
2482:
2476:
1689:
613:
39:
3061:
2901:
3303:
3106:
2501:
1662:
47:
3287:
3074:
3047:
2943:
2723:
1824:
1568:
3040:"Using dual approximation algorithms for scheduling problems: theoretical and practical results"
2545:
587:
3150:
3039:
3031:
2862:
2692:
2608:
2496:
1705:
1693:
1668:
453:
298:
3066:
3011:
2978:
2935:
2906:
2854:
2787:
2756:
2707:
2666:
2560:
301:
is one of the popular models used for describing the job-shop scheduling problem instances.
43:
3132:
2768:
2719:
1438:
1426:{\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}
247:
norm, tardiness, maximum lateness etc. It can also be multi-objective optimization problem.
3097:
2764:
2715:
2516:
2809:
2882:
2827:
2564:
2831:
3323:
2688:
2727:
3078:
3035:
2805:
1672:
3159:
1791:/2 machines), and processing time for Job P on MC2 = sum(operation times on last
2652:"Correlation of job-shop scheduling problem features with scheduling efficiency"
1631:
2670:
3016:
2999:
2983:
2965:
Optimal algorithms for online scheduling with bounded rearrangement at the end
2962:
2910:
2742:
450:
2858:
2651:
1604:
Graham had already provided the List scheduling algorithm in 1966, which is
3135:
Directory of methodologies, systems and software for dynamic optimization.
2791:
127:
job shop, where each operation can be processed on any machine of a given
3267:
2939:
2836:
Proceedings of the third annual ACM-SIAM symposium on
Discrete algorithms
728:{\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}
268:
Deterministic (fixed) processing times or probabilistic processing times.
259:
239:
135:
84:
1616:(1972) for uniform-length jobs is also optimum for two machines, and is
2947:
2711:
282:
3070:
83:
machines with varying processing power, while trying to minimize the
3000:"Online scheduling on two uniform machines to minimize the makespan"
2760:
2961:
Chen, Xin; Lan, Yan; Benkő, Attila; Dósa, György; Han, Xin (2011).
1635:
1819:
Here is an example of a job-shop scheduling problem formulated in
1820:
304:
A mathematical statement of the problem can be made as follows:
232:
Machines can require a certain gap between jobs or no idle-time.
3163:
225:
Many variations of the problem exist, including the following:
2832:"Improved parallel integer sorting without concurrent writing"
1596:, so that each waits for the output of the other's next step.
2838:. Symposium on Discrete Algorithms archive. pp. 463–472.
2745:(1977), "Worst case analysis of two scheduling algorithms",
1505:
1222:
1161:
982:
569:
538:
2485:
is a similar problem but also without the order constraint.
456:. On account of the industrial origins of the problem, the
79:
of varying processing times, which need to be scheduled on
2605:
Operations and
Production Systems with Multiple Objectives
1565:. In fact, it is quite simple to concoct examples of such
134:
The name originally came from the scheduling of jobs in a
1738:
From all available operation durations, pick the minimum.
157:
in the first field. For example, the problem denoted by "
115:
which need to be processed in a specific order (known as
238:
Objective function can be to minimize the makespan, the
151:
three-field notation for optimal job scheduling problems
2810:"A Better Algorithm for an Ancient Scheduling Problem"
682:
262:). Also, the objective function can be multi-criteria.
1759:
Remove K from list A; Add K to beginning of List L2.
1571:
1526:
1489:
1441:
1299:
1244:
1243:
1213:
1183:
1182:
1152:
1117:
1116:
1088:
1087:
1024:
973:
913:
912:
884:
883:
829:
828:
774:
773:
745:
744:
670:
639:
638:
617:
616:
590:
560:
532:
531:
496:
495:
463:
462:
384:
313:
163:
1772:
Join List L1, List L2. This is the optimum sequence.
1732:
List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}.
1630:
In 1976 Garey provided a proof that this problem is
265:
Set of jobs can relate to different set of machines.
54:. In a general job scheduling problem, we are given
3296:
3260:
3229:
3198:
2853:. Berlin / Heidelberg: Springer. pp. 202–210.
1584:
1557:
1512:
1454:
1425:
1275:
1229:
1199:
1168:
1131:
1102:
1073:
1010:
953:
898:
869:
814:
759:
727:
653:
624:
602:
576:
546:
510:
477:
441:
370:
209:
1725:, to be done on Machine M1, M2 in that sequence.
202:
2885:(1999). "Better bounds for online scheduling".
2650:Mirshekarian, Sadegh; Šormaz, Dušan N. (2016).
1749:Remove K from list A; Add K to end of List L1.
954:{\displaystyle \displaystyle J_{2},J_{3},J_{1}}
870:{\displaystyle \displaystyle J_{1},J_{2},J_{3}}
815:{\displaystyle \displaystyle J_{1},J_{2},J_{3}}
2693:"Optimal scheduling for two-processor systems"
2546:"Bounds for certain multiprocessing anomalies"
547:{\displaystyle \displaystyle \ {\mathcal {X}}}
442:{\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}
371:{\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}
142:problems, and was the first problem for which
3175:
1692:problem. Various algorithms exist, including
1513:{\displaystyle x_{\infty }\in {\mathcal {X}}}
250:Jobs may have constraints, for example a job
8:
2998:Liu, M.; Xu, Y.; Chu, C.; Zheng, F. (2009).
2539:
2537:
436:
391:
365:
320:
235:Machines can have sequence-dependent setups.
1806:Machine learning has been recently used to
661:will do, in order. For example, the matrix
3182:
3168:
3160:
1276:{\displaystyle \displaystyle C(x)>C(y)}
131:(the machines in each set are identical).
3105:
3060:
3015:
2982:
2900:
1576:
1570:
1537:
1525:
1504:
1503:
1494:
1488:
1446:
1440:
1411:
1395:
1377:
1362:
1346:
1334:
1324:
1317:
1298:
1242:
1221:
1220:
1212:
1181:
1160:
1159:
1151:
1122:
1115:
1093:
1086:
1029:
1023:
981:
980:
972:
944:
931:
918:
911:
889:
882:
860:
847:
834:
827:
805:
792:
779:
772:
750:
743:
677:
669:
644:
637:
615:
589:
568:
567:
559:
537:
536:
530:
501:
494:
468:
461:
430:
411:
398:
383:
359:
340:
327:
312:
201:
192:
183:
174:
168:
162:
2786:. Theory of Computing. pp. 51–58.
2533:
1558:{\displaystyle C(x_{\infty })=+\infty }
1683:Jobs consisting of multiple operations
210:{\displaystyle J_{3}|p_{ij}|C_{\max }}
153:, the job-shop variant is denoted by
7:
2645:
2643:
1827:problem with indicator constraints:
1766:Repeat Step 2 until List A is empty.
1677:polynomial-time approximation scheme
1074:{\displaystyle C_{ij}:M\times J\to }
1011:{\displaystyle C:{\mathcal {X}}\to }
1592:by ensuring that two machines will
1230:{\displaystyle y\in {\mathcal {X}}}
1207:is a minimum, that is, there is no
1169:{\displaystyle x\in {\mathcal {X}}}
1132:{\displaystyle \displaystyle J_{j}}
1103:{\displaystyle \displaystyle M_{i}}
899:{\displaystyle \displaystyle M_{2}}
760:{\displaystyle \displaystyle M_{1}}
654:{\displaystyle \displaystyle M_{i}}
577:{\displaystyle x\in {\mathcal {X}}}
511:{\displaystyle \displaystyle J_{j}}
478:{\displaystyle \displaystyle M_{i}}
3149:. Heidelberg, Springer. Fifth ed.
2927:Mathematics of Operations Research
2565:10.1002/j.1538-7305.1966.tb01709.x
1577:
1552:
1538:
1495:
1200:{\displaystyle \displaystyle C(x)}
1065:
1002:
14:
2522:Scheduling (production processes)
1717:has two operations, of duration P
1146:is to find an assignment of jobs
2808:; S. Phillips; E. Torng (1994).
2659:Expert Systems with Applications
964:Suppose also that there is some
91:, each job consists of a set of
625:{\displaystyle \displaystyle i}
2637:10.1016/S0377-2217(99)00486-5.
1543:
1530:
1269:
1263:
1254:
1248:
1193:
1187:
1068:
1053:
1050:
1005:
990:
987:
906:will do the jobs in the order
193:
175:
1:
2553:Bell System Technical Journal
1645:Offline makespan minimization
2971:Theoretical Computer Science
2512:List of NP-complete problems
2507:Genetic algorithm scheduling
1479:The problem of infinite cost
1462:is the idle time of machine
1081:, the cost/time for machine
632:lists the jobs that machine
285:, the job-shop problem with
1742:If the minimum belongs to P
1585:{\displaystyle x_{\infty }}
254:needs to finish before job
32:job-shop scheduling problem
3351:
2849:Fleischer, Rudolf (2000).
2671:10.1016/j.eswa.2016.06.014
1703:
1653:
610:matrices, in which column
279:traveling salesman problem
140:combinatorial optimization
3017:10.1016/j.tcs.2009.01.007
2984:10.1016/j.tcs.2011.07.014
2911:10.1137/S0097539797324874
2888:SIAM Journal on Computing
2830:; Torben Hagerup (1992).
2748:SIAM Journal on Computing
2607:. John Wiley & Sons.
1825:mixed-integer programming
1699:
1656:Multiprocessor scheduling
603:{\displaystyle n\times m}
2859:10.1007/3-540-45253-2_19
1829:
1614:Coffman–Graham algorithm
287:sequence-dependent setup
119:). Each operation has a
3309:Truthful job scheduling
3261:Optimization objectives
1752:If minimum belongs to P
767:will do the three jobs
3191:Optimal job scheduling
2816:. Discrete Algorithms.
1586:
1559:
1514:
1456:
1427:
1277:
1231:
1201:
1170:
1133:
1104:
1075:
1012:
955:
900:
871:
816:
761:
729:
655:
626:
604:
578:
548:
512:
479:
443:
372:
293:Problem representation
211:
117:precedence constraints
52:optimal job scheduling
3147:Scheduling Algorithms
2851:Algorithms – ESA 2000
2792:10.1145/129712.129718
2603:Malakooti, B (2013).
1587:
1560:
1515:
1457:
1455:{\displaystyle l_{i}}
1428:
1287:Scheduling efficiency
1278:
1232:
1202:
1171:
1134:
1105:
1076:
1013:
956:
901:
872:
817:
762:
730:
656:
627:
605:
579:
549:
513:
480:
444:
373:
212:
50:. It is a variant of
3335:NP-complete problems
3133:University of Vienna
3010:(21–23): 2099–2109.
3004:Theoret. Comput. Sci
2940:10.1287/moor.1.2.117
2814:Proc. Fifth ACM Symp
2579:"Taillard Instances"
2483:Open-shop scheduling
2477:Flow-shop scheduling
1780: > 2.)
1690:flow-shop scheduling
1569:
1524:
1487:
1470:is the makespan and
1439:
1297:
1241:
1211:
1180:
1150:
1114:
1085:
1022:
971:
910:
881:
826:
771:
742:
668:
636:
614:
588:
558:
529:
493:
460:
382:
311:
258:can be started (see
161:
144:competitive analysis
40:optimization problem
24:the job-shop problem
16:Optimization problem
3304:Interval scheduling
2784:Proc. 24th ACM Symp
2544:Graham, R. (1966).
2502:Dynamic programming
1802:Makespan prediction
1700:Johnson's algorithm
1663:bin packing problem
738:means that machine
89:job-shop scheduling
48:operations research
20:Job-shop scheduling
3330:Optimal scheduling
3297:Other requirements
3221:Unrelated machines
3211:Identical machines
3139:Taillard instances
3048:Journal of the ACM
2712:10.1007/bf00288685
2685:Coffman, E. G. Jr.
1694:genetic algorithms
1582:
1555:
1510:
1452:
1423:
1406:
1357:
1329:
1273:
1272:
1227:
1197:
1196:
1166:
1129:
1128:
1100:
1099:
1071:
1008:
951:
950:
896:
895:
867:
866:
812:
811:
757:
756:
725:
719:
651:
650:
622:
621:
600:
584:may be written as
574:
544:
543:
508:
507:
475:
474:
439:
368:
221:Problem variations
207:
3317:
3316:
3155:978-3-540-24804-0
3071:10.1145/7531.7535
2977:(45): 6269–6278.
2868:978-3-540-41004-1
2614:978-1-118-58537-5
2497:Disjunctive graph
1669:Dorit S. Hochbaum
1421:
1391:
1372:
1342:
1320:
535:
299:disjunctive graph
108:, ...,
72:, ...,
3342:
3230:Multi-stage jobs
3216:Uniform machines
3184:
3177:
3170:
3161:
3121:
3118:
3112:
3111:
3109:
3089:
3083:
3082:
3064:
3044:
3028:
3022:
3021:
3019:
2995:
2989:
2988:
2986:
2958:
2952:
2951:
2921:
2915:
2914:
2904:
2879:
2873:
2872:
2846:
2840:
2839:
2824:
2818:
2817:
2802:
2796:
2795:
2779:
2773:
2771:
2738:
2732:
2730:
2700:Acta Informatica
2697:
2681:
2675:
2674:
2656:
2647:
2638:
2634:
2628:
2625:
2619:
2618:
2600:
2594:
2593:
2589:
2583:
2582:
2575:
2569:
2568:
2559:(9): 1563–1581.
2550:
2541:
2471:Related problems
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2376:
2373:
2370:
2367:
2364:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2330:
2326:
2322:
2318:
2315:
2311:
2308:
2305:
2302:
2298:
2295:
2292:
2288:
2284:
2280:
2276:
2273:
2270:
2267:
2263:
2259:
2255:
2251:
2247:
2244:
2241:
2238:
2234:
2231:
2228:
2224:
2220:
2216:
2212:
2209:
2206:
2203:
2199:
2195:
2191:
2188:
2185:
2181:
2178:
2175:
2171:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2133:
2130:
2127:
2124:
2120:
2117:
2114:
2110:
2106:
2102:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2048:
2044:
2040:
2037:
2033:
2029:
2026:
2023:
2020:
2016:
2012:
2008:
2004:
2000:
1996:
1993:
1990:
1987:
1983:
1979:
1976:
1973:
1970:
1966:
1963:
1960:
1956:
1952:
1949:
1946:
1943:
1939:
1935:
1931:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1905:
1901:
1898:
1895:
1892:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1866:
1863:
1860:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1623:
1611:
1591:
1589:
1588:
1583:
1581:
1580:
1564:
1562:
1561:
1556:
1542:
1541:
1519:
1517:
1516:
1511:
1509:
1508:
1499:
1498:
1473:
1469:
1465:
1461:
1459:
1458:
1453:
1451:
1450:
1432:
1430:
1429:
1424:
1422:
1420:
1419:
1418:
1405:
1389:
1378:
1373:
1371:
1370:
1369:
1356:
1340:
1339:
1338:
1328:
1318:
1307:
1282:
1280:
1279:
1274:
1236:
1234:
1233:
1228:
1226:
1225:
1206:
1204:
1203:
1198:
1175:
1173:
1172:
1167:
1165:
1164:
1144:job-shop problem
1138:
1136:
1135:
1130:
1127:
1126:
1109:
1107:
1106:
1101:
1098:
1097:
1080:
1078:
1077:
1072:
1037:
1036:
1017:
1015:
1014:
1009:
986:
985:
960:
958:
957:
952:
949:
948:
936:
935:
923:
922:
905:
903:
902:
897:
894:
893:
877:, while machine
876:
874:
873:
868:
865:
864:
852:
851:
839:
838:
821:
819:
818:
813:
810:
809:
797:
796:
784:
783:
766:
764:
763:
758:
755:
754:
734:
732:
731:
726:
724:
723:
660:
658:
657:
652:
649:
648:
631:
629:
628:
623:
609:
607:
606:
601:
583:
581:
580:
575:
573:
572:
553:
551:
550:
545:
542:
541:
533:
517:
515:
514:
509:
506:
505:
484:
482:
481:
476:
473:
472:
448:
446:
445:
440:
435:
434:
416:
415:
403:
402:
377:
375:
374:
369:
364:
363:
345:
344:
332:
331:
216:
214:
213:
208:
206:
205:
196:
191:
190:
178:
173:
172:
149:In the standard
121:specific machine
44:computer science
3350:
3349:
3345:
3344:
3343:
3341:
3340:
3339:
3320:
3319:
3318:
3313:
3292:
3256:
3225:
3194:
3188:
3129:
3124:
3119:
3115:
3098:Springer Verlag
3091:
3090:
3086:
3062:10.1.1.125.5753
3042:
3032:Hochbaum, Dorit
3030:
3029:
3025:
2997:
2996:
2992:
2960:
2959:
2955:
2923:
2922:
2918:
2902:10.1.1.685.8756
2883:Albers, Susanne
2881:
2880:
2876:
2869:
2848:
2847:
2843:
2828:Albers, Susanne
2826:
2825:
2821:
2804:
2803:
2799:
2781:
2780:
2776:
2761:10.1137/0206037
2740:
2739:
2735:
2695:
2683:
2682:
2678:
2654:
2649:
2648:
2641:
2635:
2631:
2626:
2622:
2615:
2602:
2601:
2597:
2591:
2590:
2586:
2577:
2576:
2572:
2548:
2543:
2542:
2535:
2531:
2526:
2517:Optimal control
2492:
2473:
2468:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2328:
2324:
2320:
2316:
2313:
2309:
2306:
2303:
2300:
2296:
2293:
2290:
2286:
2282:
2278:
2274:
2271:
2268:
2265:
2261:
2257:
2253:
2249:
2245:
2242:
2239:
2236:
2232:
2229:
2226:
2222:
2218:
2214:
2210:
2207:
2204:
2201:
2197:
2193:
2189:
2186:
2183:
2179:
2176:
2173:
2169:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2131:
2128:
2125:
2122:
2118:
2115:
2112:
2108:
2104:
2100:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2074:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2046:
2042:
2038:
2035:
2031:
2027:
2024:
2021:
2018:
2014:
2010:
2006:
2002:
1998:
1994:
1991:
1988:
1985:
1981:
1977:
1974:
1971:
1968:
1964:
1961:
1958:
1954:
1950:
1947:
1944:
1941:
1937:
1933:
1929:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1903:
1899:
1896:
1893:
1890:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1864:
1861:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1817:
1804:
1755:
1745:
1724:
1720:
1716:
1708:
1702:
1685:
1658:
1652:
1647:
1617:
1605:
1602:
1572:
1567:
1566:
1533:
1522:
1521:
1490:
1485:
1484:
1481:
1471:
1467:
1463:
1442:
1437:
1436:
1407:
1390:
1379:
1358:
1341:
1330:
1319:
1300:
1295:
1294:
1289:
1239:
1238:
1209:
1208:
1178:
1177:
1148:
1147:
1118:
1112:
1111:
1089:
1083:
1082:
1025:
1020:
1019:
969:
968:
940:
927:
914:
908:
907:
885:
879:
878:
856:
843:
830:
824:
823:
801:
788:
775:
769:
768:
746:
740:
739:
718:
717:
712:
706:
705:
700:
694:
693:
688:
678:
666:
665:
640:
634:
633:
612:
611:
586:
585:
556:
555:
527:
526:
497:
491:
490:
464:
458:
457:
426:
407:
394:
380:
379:
355:
336:
323:
309:
308:
295:
275:
244:
223:
197:
179:
164:
159:
158:
113:
107:
100:
77:
71:
64:
17:
12:
11:
5:
3348:
3346:
3338:
3337:
3332:
3322:
3321:
3315:
3314:
3312:
3311:
3306:
3300:
3298:
3294:
3293:
3291:
3290:
3285:
3280:
3275:
3270:
3264:
3262:
3258:
3257:
3255:
3254:
3249:
3244:
3239:
3237:Parallel tasks
3233:
3231:
3227:
3226:
3224:
3223:
3218:
3213:
3208:
3206:Single machine
3202:
3200:
3199:One-stage jobs
3196:
3195:
3189:
3187:
3186:
3179:
3172:
3164:
3158:
3157:
3141:
3136:
3128:
3127:External links
3125:
3123:
3122:
3113:
3107:10.1.1.29.4699
3084:
3055:(1): 144–162.
3023:
2990:
2953:
2934:(2): 117–129.
2916:
2895:(2): 459–473.
2874:
2867:
2841:
2819:
2797:
2774:
2755:(3): 518–536,
2733:
2706:(3): 200–213,
2676:
2639:
2629:
2620:
2613:
2595:
2584:
2570:
2532:
2530:
2527:
2525:
2524:
2519:
2514:
2509:
2504:
2499:
2493:
2491:
2488:
2487:
2486:
2480:
2472:
2469:
2381:ProcessingTime
2200:ProcessingTime
2049:ProcessingTime
2045:CumulativeTime
2041:CumulativeTime
1984:ProcessingTime
1923:CumulativeTime
1897:ProcessingTime
1830:
1816:
1813:
1803:
1800:
1795:/2 machines).
1774:
1773:
1767:
1753:
1743:
1740:
1739:
1733:
1722:
1718:
1714:
1706:Johnson's rule
1701:
1698:
1684:
1681:
1651:
1648:
1646:
1643:
1601:
1598:
1579:
1575:
1554:
1551:
1548:
1545:
1540:
1536:
1532:
1529:
1507:
1502:
1497:
1493:
1480:
1477:
1449:
1445:
1417:
1414:
1410:
1404:
1401:
1398:
1394:
1388:
1385:
1382:
1376:
1368:
1365:
1361:
1355:
1352:
1349:
1345:
1337:
1333:
1327:
1323:
1316:
1313:
1310:
1306:
1303:
1288:
1285:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1224:
1219:
1216:
1195:
1192:
1189:
1186:
1163:
1158:
1155:
1125:
1121:
1096:
1092:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1035:
1032:
1028:
1007:
1004:
1001:
998:
995:
992:
989:
984:
979:
976:
947:
943:
939:
934:
930:
926:
921:
917:
892:
888:
863:
859:
855:
850:
846:
842:
837:
833:
808:
804:
800:
795:
791:
787:
782:
778:
753:
749:
736:
735:
722:
716:
713:
711:
708:
707:
704:
701:
699:
696:
695:
692:
689:
687:
684:
683:
681:
676:
673:
647:
643:
620:
599:
596:
593:
571:
566:
563:
540:
504:
500:
471:
467:
438:
433:
429:
425:
422:
419:
414:
410:
406:
401:
397:
393:
390:
387:
367:
362:
358:
354:
351:
348:
343:
339:
335:
330:
326:
322:
319:
316:
294:
291:
274:
271:
270:
269:
266:
263:
248:
242:
236:
233:
230:
222:
219:
204:
200:
195:
189:
186:
182:
177:
171:
167:
111:
105:
98:
75:
69:
62:
15:
13:
10:
9:
6:
4:
3:
2:
3347:
3336:
3333:
3331:
3328:
3327:
3325:
3310:
3307:
3305:
3302:
3301:
3299:
3295:
3289:
3286:
3284:
3281:
3279:
3276:
3274:
3271:
3269:
3266:
3265:
3263:
3259:
3253:
3250:
3248:
3245:
3243:
3240:
3238:
3235:
3234:
3232:
3228:
3222:
3219:
3217:
3214:
3212:
3209:
3207:
3204:
3203:
3201:
3197:
3192:
3185:
3180:
3178:
3173:
3171:
3166:
3165:
3162:
3156:
3152:
3148:
3145:
3142:
3140:
3137:
3134:
3131:
3130:
3126:
3117:
3114:
3108:
3103:
3099:
3095:
3088:
3085:
3080:
3076:
3072:
3068:
3063:
3058:
3054:
3050:
3049:
3041:
3037:
3036:Shmoys, David
3033:
3027:
3024:
3018:
3013:
3009:
3005:
3001:
2994:
2991:
2985:
2980:
2976:
2972:
2968:
2966:
2957:
2954:
2949:
2945:
2941:
2937:
2933:
2929:
2928:
2920:
2917:
2912:
2908:
2903:
2898:
2894:
2890:
2889:
2884:
2878:
2875:
2870:
2864:
2860:
2856:
2852:
2845:
2842:
2837:
2833:
2829:
2823:
2820:
2815:
2811:
2807:
2801:
2798:
2793:
2789:
2785:
2778:
2775:
2770:
2766:
2762:
2758:
2754:
2750:
2749:
2744:
2737:
2734:
2729:
2725:
2721:
2717:
2713:
2709:
2705:
2701:
2694:
2690:
2689:Graham, R. L.
2686:
2680:
2677:
2672:
2668:
2664:
2660:
2653:
2646:
2644:
2640:
2633:
2630:
2624:
2621:
2616:
2610:
2606:
2599:
2596:
2588:
2585:
2580:
2574:
2571:
2566:
2562:
2558:
2554:
2547:
2540:
2538:
2534:
2528:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2498:
2495:
2494:
2489:
2484:
2481:
2478:
2475:
2474:
2470:
2272:no21_conflict
2208:no12_conflict
1828:
1826:
1822:
1814:
1812:
1811:the average.
1809:
1801:
1799:
1796:
1794:
1790:
1786:
1781:
1779:
1771:
1768:
1765:
1762:
1761:
1760:
1757:
1750:
1747:
1737:
1734:
1731:
1728:
1727:
1726:
1711:
1707:
1697:
1695:
1691:
1682:
1680:
1678:
1674:
1670:
1666:
1664:
1657:
1649:
1644:
1642:
1639:
1637:
1633:
1628:
1625:
1621:
1618:(2 − 2/
1615:
1609:
1606:(2 − 1/
1600:Major results
1599:
1597:
1595:
1573:
1549:
1546:
1534:
1527:
1500:
1491:
1478:
1476:
1447:
1443:
1433:
1415:
1412:
1408:
1402:
1399:
1396:
1392:
1386:
1383:
1380:
1374:
1366:
1363:
1359:
1353:
1350:
1347:
1343:
1335:
1331:
1325:
1321:
1314:
1311:
1308:
1304:
1301:
1292:
1286:
1284:
1266:
1260:
1257:
1251:
1245:
1217:
1214:
1190:
1184:
1156:
1153:
1145:
1140:
1123:
1119:
1094:
1090:
1062:
1059:
1056:
1047:
1044:
1041:
1038:
1033:
1030:
1026:
999:
996:
993:
977:
974:
967:
966:cost function
962:
945:
941:
937:
932:
928:
924:
919:
915:
890:
886:
861:
857:
853:
848:
844:
840:
835:
831:
822:in the order
806:
802:
798:
793:
789:
785:
780:
776:
751:
747:
720:
714:
709:
702:
697:
690:
685:
679:
674:
671:
664:
663:
662:
645:
641:
618:
597:
594:
591:
564:
561:
523:
521:
502:
498:
488:
469:
465:
455:
452:
431:
427:
423:
420:
417:
412:
408:
404:
399:
395:
388:
385:
360:
356:
352:
349:
346:
341:
337:
333:
328:
324:
317:
314:
305:
302:
300:
292:
290:
288:
284:
280:
272:
267:
264:
261:
257:
253:
249:
246:
245:
237:
234:
231:
228:
227:
226:
220:
218:
198:
187:
184:
180:
169:
165:
156:
152:
147:
145:
141:
137:
132:
130:
126:
122:
118:
114:
104:
97:
94:
90:
86:
82:
78:
68:
61:
57:
53:
49:
45:
41:
37:
33:
29:
25:
21:
3251:
3143:
3116:
3093:
3087:
3052:
3046:
3026:
3007:
3003:
2993:
2974:
2970:
2964:
2956:
2931:
2925:
2919:
2892:
2886:
2877:
2850:
2844:
2835:
2822:
2813:
2800:
2783:
2777:
2752:
2746:
2736:
2703:
2699:
2679:
2662:
2658:
2632:
2623:
2604:
2598:
2587:
2573:
2556:
2552:
2163:makespan_def
1818:
1807:
1805:
1797:
1792:
1788:
1784:
1782:
1777:
1775:
1769:
1763:
1758:
1751:
1748:
1741:
1735:
1729:
1712:
1709:
1686:
1675:presented a
1673:David Shmoys
1667:
1659:
1640:
1629:
1626:
1619:
1607:
1603:
1482:
1434:
1293:
1290:
1143:
1141:
965:
963:
737:
524:
519:
486:
306:
303:
296:
276:
255:
251:
240:
224:
154:
148:
133:
128:
124:
120:
116:
109:
102:
95:
92:
88:
80:
73:
66:
59:
55:
35:
31:
27:
23:
19:
18:
2743:Sethi, Ravi
2741:Lam, Shui;
2665:: 131–147.
1650:Atomic jobs
1632:NP-complete
518:are called
485:are called
273:NP-hardness
3324:Categories
3288:Throughput
3144:Brucker P.
3096:. London:
2806:Karger, D.
2529:References
2363:N_MACHINES
2331:TimeOffset
2264:TimeOffset
1992:TimeOffset
1889:N_MACHINES
1844:N_MACHINES
1704:See also:
1654:See also:
1520:such that
1237:such that
1176:such that
1110:to do job
277:Since the
93:operations
3283:Tardiness
3273:Earliness
3247:Flow shop
3242:Open shop
3102:CiteSeerX
3057:CiteSeerX
2897:CiteSeerX
1578:∞
1553:∞
1539:∞
1501:∈
1496:∞
1393:∑
1344:∑
1322:∑
1218:∈
1157:∈
1066:∞
1051:→
1045:×
1003:∞
988:→
595:×
565:∈
421:…
350:…
3278:Lateness
3268:Makespan
3252:Job shop
3193:problems
3038:(1987).
2728:40603807
2691:(1972),
2490:See also
2319:precedes
2252:precedes
2196:MACHINES
2148:makespan
2145:minimize
2094:precedes
2034:MACHINES
2015:<>
1957:MACHINES
1940:MACHINES
1906:MACHINES
1875:MACHINES
1594:deadlock
1305:′
489:and the
487:machines
260:workflow
136:job shop
125:flexible
85:makespan
38:) is an
3079:9739129
2948:3689278
2769:0496614
2720:0334913
2269:subj to
2205:subj to
2160:subj to
1878:ordered
1856:ordered
1815:Example
1808:predict
1770:Step 4.
1764:Step 3.
1736:Step 2.
1730:Step 1.
449:be two
283:NP-hard
101:,
65:,
3153:
3104:
3077:
3059:
2946:
2899:
2865:
2767:
2726:
2718:
2611:
2345:N_JOBS
2321:==>
2254:==>
2139:binary
1867:N_JOBS
1835:N_JOBS
534:
451:finite
3075:S2CID
3043:(PDF)
2944:JSTOR
2724:S2CID
2696:(PDF)
2655:(PDF)
2549:(PDF)
2378:param
2360:param
2342:param
2327:start
2325:>=
2323:start
2260:start
2258:>=
2256:start
2182:start
2180:>=
2082:>=
2072:start
2060:>=
1989:param
1972:<=
1920:param
1894:param
1841:param
1832:param
1823:as a
1713:Job P
1435:Here
58:jobs
30:) or
3151:ISBN
2863:ISBN
2609:ISBN
2336:data
2304:<
2289:JOBS
2281:JOBS
2240:<
2225:JOBS
2217:JOBS
2172:JOBS
2126:<
2111:JOBS
2103:JOBS
2077:JOBS
2009:JOBS
2001:JOBS
1932:JOBS
1911:>
1902:JOBS
1853:JOBS
1821:AMPL
1671:and
1636:P=NP
1258:>
1142:The
525:Let
520:jobs
454:sets
378:and
307:Let
297:The
46:and
36:JSSP
3067:doi
3012:doi
3008:410
2979:doi
2975:412
2936:doi
2907:doi
2855:doi
2788:doi
2757:doi
2708:doi
2667:doi
2561:doi
2314:)}:
2307:ord
2294:ord
2250:)}:
2243:ord
2230:ord
2187:sum
2177:end
2154:end
2129:ord
2116:ord
2091:var
2069:var
2057:end
2054:var
2025:max
1975:ord
1962:ord
1948:sum
1872:set
1850:set
1721:, P
1665:.)
1638:).
281:is
203:max
129:set
42:in
28:JSP
3326::
3100:.
3073:.
3065:.
3053:34
3051:.
3045:.
3034:;
3006:.
3002:.
2973:.
2969:.
2942:.
2930:.
2905:.
2893:29
2891:.
2861:.
2834:.
2812:.
2765:MR
2763:,
2751:,
2722:,
2716:MR
2714:,
2702:,
2698:,
2687:;
2663:62
2661:.
2657:.
2642:^
2557:45
2555:.
2551:.
2536:^
2312:i2
2299:i1
2287:in
2285:i2
2279:in
2277:i1
2248:i2
2235:i1
2223:in
2221:i2
2215:in
2213:i1
2194:in
2174:}:
2170:in
2136:)}
2134:i2
2121:i1
2109:in
2107:i2
2101:in
2099:i1
2051:);
2032:in
2017:i2
2013:i1
2007:in
2005:i2
1999:in
1997:i1
1982:)}
1967:jj
1955:in
1953:jj
1938:in
1930:in
1887:..
1865:..
1756:,
1754:k2
1746:,
1744:k1
1723:i2
1719:i1
1696:.
1466:,
1283:.
1139:.
961:.
522:.
22:,
3183:e
3176:t
3169:v
3110:.
3081:.
3069::
3020:.
3014::
2987:.
2981::
2967:"
2963:"
2950:.
2938::
2932:1
2913:.
2909::
2871:.
2857::
2794:.
2790::
2772:.
2759::
2753:6
2731:.
2710::
2704:1
2673:.
2669::
2617:.
2581:.
2567:.
2563::
2465:;
2462:8
2459:5
2456:1
2453:3
2450:4
2447:3
2444:2
2441:7
2438:9
2435:3
2432:2
2429:6
2426:3
2423:8
2420:2
2417:1
2414:2
2411:4
2408:5
2405:1
2402:=
2399::
2396:4
2393:3
2390:2
2387:1
2384::
2375:;
2372:4
2369:=
2366::
2357:;
2354:4
2351:=
2348::
2339:;
2333:;
2329:+
2317:!
2310:(
2301:)
2297:(
2291::
2283:,
2275:{
2266:;
2262:+
2246:(
2237:)
2233:(
2227::
2219:,
2211:{
2202:;
2198:}
2192:j
2190:{
2184:+
2168:i
2166:{
2157:;
2151::
2142:;
2132:(
2123:)
2119:(
2113::
2105:,
2097:{
2088:;
2085:0
2079:}
2075:{
2066:;
2063:0
2047:+
2043:-
2039:(
2036:}
2030:j
2028:{
2022:=
2019:}
2011::
2003:,
1995:{
1986:;
1980:j
1978:(
1969:)
1965:(
1959::
1951:{
1945:=
1942:}
1936:j
1934:,
1928:i
1926:{
1917:;
1914:0
1908:}
1904:,
1900:{
1891:;
1884:1
1881:=
1869:;
1862:1
1859:=
1847:;
1838:;
1793:m
1789:m
1785:m
1778:M
1715:i
1622:)
1620:m
1610:)
1608:m
1574:x
1550:+
1547:=
1544:)
1535:x
1531:(
1528:C
1506:X
1492:x
1472:m
1468:C
1464:i
1448:i
1444:l
1416:k
1413:j
1409:p
1403:k
1400:,
1397:j
1387:m
1384:.
1381:C
1375:=
1367:k
1364:j
1360:p
1354:k
1351:,
1348:j
1336:i
1332:l
1326:i
1315:+
1312:1
1309:=
1302:C
1270:)
1267:y
1264:(
1261:C
1255:)
1252:x
1249:(
1246:C
1223:X
1215:y
1194:)
1191:x
1188:(
1185:C
1162:X
1154:x
1124:j
1120:J
1095:i
1091:M
1069:]
1063:+
1060:,
1057:0
1054:[
1048:J
1042:M
1039::
1034:j
1031:i
1027:C
1006:]
1000:+
997:,
994:0
991:[
983:X
978::
975:C
946:1
942:J
938:,
933:3
929:J
925:,
920:2
916:J
891:2
887:M
862:3
858:J
854:,
849:2
845:J
841:,
836:1
832:J
807:3
803:J
799:,
794:2
790:J
786:,
781:1
777:J
752:1
748:M
721:)
715:1
710:3
703:3
698:2
691:2
686:1
680:(
675:=
672:x
646:i
642:M
619:i
598:m
592:n
570:X
562:x
539:X
503:j
499:J
470:i
466:M
437:}
432:n
428:J
424:,
418:,
413:2
409:J
405:,
400:1
396:J
392:{
389:=
386:J
366:}
361:m
357:M
353:,
347:,
342:2
338:M
334:,
329:1
325:M
321:{
318:=
315:M
256:j
252:i
243:p
241:L
199:C
194:|
188:j
185:i
181:p
176:|
170:3
166:J
155:J
112:n
110:O
106:2
103:O
99:1
96:O
81:m
76:n
74:J
70:2
67:J
63:1
60:J
56:n
34:(
26:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.