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