1640:
Note that the number of configurations is usually exponential in the size of the problem, so the size of the configuration LP is exponential. However, in some cases it is possible to bound the number of possible configurations, and therefore find an approximate solution in polynomial time.
980:. We would like to allocate the items to the people, such that the least-happy person is as happy as possible. This problem is equivalent to unrelated-machines scheduling in which the goal is to maximize the minimum completion time. It is better known by the name
653:
Lenstra, Shmoys and Tardos presented a polytime 2-factor approximation algorithm, and proved that no polytime algorithm with approximation factor smaller than 3/2 is possible unless P=NP. Closing the gap between the 2 and the 3/2 is a long-standing open problem.
1566:
1203:
1453:
501:
1115:
743:
1626:
1277:
Relaxing the integer constraints gives a linear program with size polynomial in the input. Solving the relaxed problem can be rounded to obtain a 2-approximation to the problem.
1263:
647:
545:
937:
834:
291:
603:
439:
780:
242:
1696:
332:
194:
1706:
Kim, Kim, Jang and Chen extend the problem by allowing each job to have a setup time, which depends on the job but not on the machine. They present a solution using
1371:
1044:
896:
2363:
459:
381:
completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
649:. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.
384:
1467:
2356:
1129:
196:" is an unrelated-machines scheduling problem with no constraints, where the goal is to minimize the maximum completion time.
2392:
138:
2349:
1734:
1718:
1283:
2511:
2397:
964:
661:
335:
102:
1387:
464:
2387:
947:
Bar-Noy, Bar-Yehuda, Freund, Naor and
Schieber consider a setting in which, for each job and machine, there is a
2418:
2262:"A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times"
246:
1909:
Glass, C.A.; Potts, C.N.; Shade, P. (1994-07-01). "Unrelated parallel machine scheduling using local search".
1853:
1060:
664:
techniques for minimizing the makespan on unrelated machines. Using computerized simulations, they find that
2490:
1722:
986:
687:
2464:
2454:
2372:
2318:
2261:
2222:
159:
35:
969:
Suppose that, instead of "jobs" we have valuable items, and instead of "machines" we have people. Person
2459:
1580:
1217:
608:
506:
2183:
2428:
2423:
902:
799:
256:
23:
1721:. extend the problem in a different way, by assuming that the jobs are owned by selfish agents (see
562:
2485:
2433:
2323:
1707:
866:
669:
374:
31:
2469:
2164:
2114:
2024:
1975:
1891:
1865:
1834:
1787:
951:
for running this job on that machine. They present a 1/2 approximation for discrete input and (1-
402:
244:. More generally, when some jobs are more important than others, it may be desired to minimize a
755:
217:
1674:
310:
172:
2291:
2242:
2203:
2156:
2106:
2063:
2016:
1967:
1926:
1883:
1826:
1779:
1711:
859:
673:
360:
1343:
1016:
2328:
2281:
2273:
2234:
2195:
2148:
2098:
2055:
2006:
1957:
1918:
1875:
1818:
1769:
858:
It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the
852:
27:
2043:
1660:, and its run-time in each of these machines is 1. This variant is sometimes denoted by "
874:
2082:
444:
2238:
2199:
67:
different machines, such that a certain objective function is optimized (usually, the
2505:
2168:
1922:
1895:
2118:
2028:
1838:
1791:
1979:
869:. Their algorithm is a (2+ε)-approximation for the problem with job release times,
2341:
2223:"Unrelated parallel machine scheduling with setup times using simulated annealing"
1656:
is either 1 or infinity. In other words, each job can be processed on a subset of
250:
of the completion time, where each job has a different weight. This is denoted by
665:
2277:
2059:
1879:
2295:
2246:
2207:
2160:
2110:
2067:
2020:
1971:
1930:
1887:
1830:
1783:
2221:
Kim, Dong-Won; Kim, Kyong-Hee; Jang, Wooseung; Frank Chen, F. (2002-06-01).
2332:
1290:, there are finitely many subsets of jobs that can be processed by machine
657:
Verschae and Wiese presented a different 2-factor approximation algorithm.
2102:
2011:
1994:
1962:
1945:
1774:
1757:
2449:
1758:"Exact and Approximate Algorithms for Scheduling Nonidentical Processors"
998:
A natural way to formulate the problem as a linear program is called the
68:
2184:"Parallel machine scheduling of machine-dependent jobs with unit-length"
2087:"A unified approach to approximating resource allocation and scheduling"
2086:
2286:
2152:
2081:
Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; (Seffi) Naor, Joseph;
1822:
2137:"Approximation algorithms for scheduling unrelated parallel machines"
2136:
1807:"Approximation algorithms for scheduling unrelated parallel machines"
1806:
1561:{\displaystyle \sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1}
865:
Schulz and
Skutella present a (3/2+ε)-approximation algorithm using
1870:
548:
2309:
Nisan, Noam; Ronen, Amir (2001). "Algorithmic
Mechanism Design".
2135:
Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01).
1805:
Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01).
16:
Optimization problem in computer science and operations research
2345:
684:
Bruno, Coffman and Sethi present an algorithm, running in time
1854:"On the configuration-LP for scheduling on unrelated machines"
1946:"Scheduling independent tasks to reduce mean finishing time"
101:. This is in contrast to two special cases of this problem:
1373:
which equals 1 if the actual configuration used in machine
199:
In some variants of the problem, instead of minimizing the
166:
in the first field. For example, the problem denoted by "
1198:{\displaystyle \sum _{j=1}^{n}z_{i,j}\cdot p_{i,j}\leq T}
160:
three-field notation for optimal job scheduling problems
86:
emphasizes that there is no relation between values of
2044:"Scheduling Unrelated Machines by Randomized Rounding"
1735:
Summary of parallel machine problems without preemtion
1677:
1583:
1470:
1390:
1346:
1220:
1132:
1063:
1019:
905:
877:
802:
758:
690:
611:
565:
509:
467:
447:
405:
313:
259:
220:
175:
745:, for minimizing the average job completion time on
2478:
2442:
2411:
2380:
2042:Schulz, Andreas S.; Skutella, Martin (2002-01-01).
1944:Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01).
391:>0, attain at most (1+ε)OPT. For minimizing the
1690:
1620:
1560:
1447:
1365:
1257:
1197:
1109:
1038:
931:
890:
828:
774:
737:
641:
597:
539:
495:
453:
433:
326:
285:
236:
188:
1381:, and 0 otherwise. Then, the LP constraints are:
1054:, and 0 otherwise. Then, the LP constraints are:
347:Minimizing the maximum completion time (makespan)
1683:
697:
319:
181:
786:, of the time it takes to complete the jobs).
334:" . This variant corresponds to the problem of
203:completion time, it is desired to minimize the
162:, the unrelated-machines variant is denoted by
2227:Robotics and Computer-Integrated Manufacturing
1710:. Vallada and Ruiz present a solution using a
1448:{\displaystyle \sum _{c\in C_{i}(T)}x_{i,c}=1}
75:needs in order to process job j is denoted by
2357:
1995:"Algorithms for Scheduling Independent Tasks"
1852:Verschae, José; Wiese, Andreas (2013-11-10).
1756:Horowitz, Ellis; Sahni, Sartaj (1976-04-01).
1000:Lenstra–Shmoys–Tardos linear program (LST LP)
8:
1615:
1603:
1317:) the set of all configurations for machine
1252:
1240:
496:{\displaystyle \epsilon \geq 2\cdot 10^{-l}}
71:should be minimized). The time that machine
2364:
2350:
2342:
2190:. EURO Excellence in Practice Award 2001.
2322:
2285:
2010:
1961:
1869:
1773:
1698:". It can be solved in polynomial time.
1682:
1676:
1588:
1582:
1540:
1519:
1496:
1486:
1475:
1469:
1427:
1406:
1395:
1389:
1351:
1345:
1225:
1219:
1177:
1158:
1148:
1137:
1131:
1089:
1079:
1068:
1062:
1024:
1018:
923:
913:
904:
882:
876:
820:
810:
801:
766:
757:
723:
710:
689:
628:
622:
610:
586:
576:
564:
528:
519:
508:
484:
466:
446:
416:
404:
318:
312:
277:
267:
258:
228:
219:
180:
174:
2266:European Journal of Operational Research
2260:Vallada, Eva; Ruiz, Rubén (2011-06-16).
2188:European Journal of Operational Research
1110:{\displaystyle \sum _{i=1}^{m}z_{i,j}=1}
955:)/2 approximation for continuous input.
1745:
1717:Nisan and Ronen in their 1999 paper on
660:Glass, Potts and Shade compare various
399:machines, their algorithm runs in time
959:Maximizing the minimum completion time
680:Minimizing the average completion time
2182:Lin, Yixun; Li, Wenhua (2004-07-01).
738:{\displaystyle O(\max(mn^{2},n^{3}))}
385:Polynomial-time approximation schemes
155:(the same run-time on all machines).
7:
2130:
2128:
2048:SIAM Journal on Discrete Mathematics
1751:
1749:
355:completion time is NP-hard even for
1911:Mathematical and Computer Modelling
296:In a third variant, the goal is to
207:completion time (averaged over all
1621:{\displaystyle x_{i,j}\in \{0,1\}}
1258:{\displaystyle z_{i,j}\in \{0,1\}}
642:{\displaystyle O(n^{2}/\epsilon )}
540:{\displaystyle O(n/\epsilon ^{2})}
461:is the smallest integer for which
14:
1649:There is a special case in which
851:machines, by reduction from the
503:. Therefore, the run-time is in
359:machines, by reduction from the
1993:Sahni, Sartaj K. (1976-01-01).
1298:. Each such subset is called a
932:{\displaystyle \sum w_{j}C_{j}}
829:{\displaystyle \sum w_{j}C_{j}}
286:{\displaystyle \sum w_{i}C_{i}}
1531:
1525:
1418:
1412:
1282:Another LP formulation is the
994:Linear programming formulation
732:
729:
700:
694:
636:
615:
598:{\displaystyle O(10^{l}n^{2})}
592:
569:
534:
513:
428:
409:
377:algorithms for minimizing the
1:
2239:10.1016/S0736-5845(02)00013-3
2200:10.1016/S0377-2217(02)00914-1
139:identical-machines scheduling
20:Unrelated-machines scheduling
1923:10.1016/0895-7177(94)90205-4
1719:algorithmic mechanism design
1284:configuration linear program
1046:, which equals 1 if machine
2311:Games and Economic Behavior
965:Egalitarian item allocation
434:{\displaystyle O(10^{2l}n)}
336:Egalitarian item allocation
103:uniform-machines scheduling
2528:
2278:10.1016/j.ejor.2011.01.011
962:
775:{\displaystyle \sum C_{j}}
559:machines, the run-time is
237:{\displaystyle \sum C_{i}}
2060:10.1137/S0895480199357078
1950:Communications of the ACM
1880:10.1007/s10951-013-0359-4
1691:{\displaystyle C_{\max }}
672:perform much better than
327:{\displaystyle C_{\min }}
189:{\displaystyle C_{\max }}
2141:Mathematical Programming
1811:Mathematical Programming
211:jobs); it is denoted by
133:is the speed of machine
2491:Truthful job scheduling
2443:Optimization objectives
1723:Truthful job scheduling
1366:{\displaystyle x_{i,c}}
1039:{\displaystyle z_{i,j}}
987:max-min item allocation
555:completion time on two
395:completion time on two
2373:Optimal job scheduling
2333:10.1006/game.1999.0790
1692:
1622:
1562:
1491:
1449:
1367:
1259:
1199:
1153:
1111:
1084:
1040:
933:
892:
847:), is NP-hard even on
830:
782:(the average over all
776:
739:
643:
599:
541:
497:
455:
435:
328:
287:
238:
190:
38:. We need to schedule
36:optimal job scheduling
2103:10.1145/502102.502107
2012:10.1145/321921.321934
1963:10.1145/361011.361064
1858:Journal of Scheduling
1775:10.1145/321941.321951
1693:
1623:
1563:
1471:
1450:
1368:
1340:), define a variable
1260:
1200:
1133:
1112:
1064:
1041:
943:Maximizing the profit
934:
893:
891:{\displaystyle r_{j}}
843:is the weight of job
831:
777:
740:
644:
600:
551:. For minimizing the
542:
498:
456:
436:
329:
288:
239:
191:
34:. It is a variant of
1675:
1581:
1468:
1388:
1344:
1218:
1130:
1061:
1017:
903:
875:
800:
756:
688:
609:
563:
507:
465:
445:
403:
311:
304:completion time, "
257:
218:
173:
24:optimization problem
2486:Interval scheduling
1708:simulated annealing
1321:. For each machine
1286:. For each machine
1002:. For each machine
867:randomized rounding
670:simulated annealing
375:dynamic programming
32:operations research
2512:Optimal scheduling
2479:Other requirements
2403:Unrelated machines
2393:Identical machines
2153:10.1007/BF01585745
2091:Journal of the ACM
1999:Journal of the ACM
1823:10.1007/BF01585745
1762:Journal of the ACM
1688:
1618:
1558:
1535:
1455:for every machine
1445:
1422:
1363:
1325:and configuration
1255:
1205:for every machine
1195:
1107:
1036:
1013:define a variable
929:
888:
826:
772:
735:
674:genetic algorithms
639:
595:
537:
493:
451:
431:
366:Horowitz and Sahni
324:
283:
234:
186:
2499:
2498:
1712:genetic algorithm
1492:
1391:
973:values item j at
860:partition problem
793:completion time,
454:{\displaystyle l}
361:partition problem
2519:
2412:Multi-stage jobs
2398:Uniform machines
2366:
2359:
2352:
2343:
2337:
2336:
2326:
2317:(1–2): 166–196.
2306:
2300:
2299:
2289:
2257:
2251:
2250:
2233:(3–4): 223–231.
2218:
2212:
2211:
2179:
2173:
2172:
2132:
2123:
2122:
2097:(5): 1069–1090.
2083:Schieber, Baruch
2078:
2072:
2071:
2039:
2033:
2032:
2014:
1990:
1984:
1983:
1965:
1941:
1935:
1934:
1906:
1900:
1899:
1873:
1849:
1843:
1842:
1802:
1796:
1795:
1777:
1753:
1697:
1695:
1694:
1689:
1687:
1686:
1658:allowed machines
1627:
1625:
1624:
1619:
1599:
1598:
1567:
1565:
1564:
1559:
1551:
1550:
1534:
1524:
1523:
1490:
1485:
1454:
1452:
1451:
1446:
1438:
1437:
1421:
1411:
1410:
1372:
1370:
1369:
1364:
1362:
1361:
1294:in time at most
1264:
1262:
1261:
1256:
1236:
1235:
1204:
1202:
1201:
1196:
1188:
1187:
1169:
1168:
1152:
1147:
1116:
1114:
1113:
1108:
1100:
1099:
1083:
1078:
1045:
1043:
1042:
1037:
1035:
1034:
938:
936:
935:
930:
928:
927:
918:
917:
897:
895:
894:
889:
887:
886:
853:knapsack problem
835:
833:
832:
827:
825:
824:
815:
814:
791:weighted average
781:
779:
778:
773:
771:
770:
744:
742:
741:
736:
728:
727:
715:
714:
648:
646:
645:
640:
632:
627:
626:
604:
602:
601:
596:
591:
590:
581:
580:
546:
544:
543:
538:
533:
532:
523:
502:
500:
499:
494:
492:
491:
460:
458:
457:
452:
440:
438:
437:
432:
424:
423:
387:, which for any
333:
331:
330:
325:
323:
322:
292:
290:
289:
284:
282:
281:
272:
271:
247:weighted average
243:
241:
240:
235:
233:
232:
195:
193:
192:
187:
185:
184:
158:In the standard
28:computer science
2527:
2526:
2522:
2521:
2520:
2518:
2517:
2516:
2502:
2501:
2500:
2495:
2474:
2438:
2407:
2376:
2370:
2340:
2308:
2307:
2303:
2259:
2258:
2254:
2220:
2219:
2215:
2181:
2180:
2176:
2134:
2133:
2126:
2080:
2079:
2075:
2041:
2040:
2036:
1992:
1991:
1987:
1943:
1942:
1938:
1908:
1907:
1903:
1851:
1850:
1846:
1804:
1803:
1799:
1755:
1754:
1747:
1743:
1731:
1704:
1678:
1673:
1672:
1669:
1665:
1654:
1647:
1584:
1579:
1578:
1536:
1515:
1466:
1465:
1423:
1402:
1386:
1385:
1347:
1342:
1341:
1334:
1311:
1221:
1216:
1215:
1173:
1154:
1128:
1127:
1085:
1059:
1058:
1020:
1015:
1014:
1011:
996:
978:
967:
961:
945:
919:
909:
901:
900:
878:
873:
872:
841:
816:
806:
798:
797:
789:Minimizing the
762:
754:
753:
719:
706:
686:
685:
682:
618:
607:
606:
582:
572:
561:
560:
524:
505:
504:
480:
463:
462:
443:
442:
412:
401:
400:
351:Minimizing the
349:
344:
314:
309:
308:
273:
263:
255:
254:
224:
216:
215:
176:
171:
170:
153:
146:
131:
124:
117:
110:
91:
80:
61:
55:
48:
17:
12:
11:
5:
2525:
2523:
2515:
2514:
2504:
2503:
2497:
2496:
2494:
2493:
2488:
2482:
2480:
2476:
2475:
2473:
2472:
2467:
2462:
2457:
2452:
2446:
2444:
2440:
2439:
2437:
2436:
2431:
2426:
2421:
2419:Parallel tasks
2415:
2413:
2409:
2408:
2406:
2405:
2400:
2395:
2390:
2388:Single machine
2384:
2382:
2381:One-stage jobs
2378:
2377:
2371:
2369:
2368:
2361:
2354:
2346:
2339:
2338:
2324:10.1.1.16.7473
2301:
2272:(3): 612–622.
2252:
2213:
2194:(1): 261–266.
2174:
2147:(1): 259–271.
2124:
2085:(2001-09-01).
2073:
2054:(4): 450–469.
2034:
2005:(1): 116–127.
1985:
1956:(7): 382–387.
1936:
1901:
1864:(4): 371–383.
1844:
1817:(1): 259–271.
1797:
1768:(2): 317–327.
1744:
1742:
1739:
1738:
1737:
1730:
1729:External links
1727:
1703:
1700:
1685:
1681:
1667:
1663:
1652:
1646:
1643:
1638:
1637:
1617:
1614:
1611:
1608:
1605:
1602:
1597:
1594:
1591:
1587:
1576:
1568:for every job
1557:
1554:
1549:
1546:
1543:
1539:
1533:
1530:
1527:
1522:
1518:
1514:
1511:
1508:
1505:
1502:
1499:
1495:
1489:
1484:
1481:
1478:
1474:
1463:
1444:
1441:
1436:
1433:
1430:
1426:
1420:
1417:
1414:
1409:
1405:
1401:
1398:
1394:
1360:
1357:
1354:
1350:
1332:
1309:
1275:
1274:
1254:
1251:
1248:
1245:
1242:
1239:
1234:
1231:
1228:
1224:
1213:
1194:
1191:
1186:
1183:
1180:
1176:
1172:
1167:
1164:
1161:
1157:
1151:
1146:
1143:
1140:
1136:
1125:
1117:for every job
1106:
1103:
1098:
1095:
1092:
1088:
1082:
1077:
1074:
1071:
1067:
1050:processes job
1033:
1030:
1027:
1023:
1009:
995:
992:
976:
963:Main article:
960:
957:
944:
941:
926:
922:
916:
912:
908:
885:
881:
839:
823:
819:
813:
809:
805:
769:
765:
761:
734:
731:
726:
722:
718:
713:
709:
705:
702:
699:
696:
693:
681:
678:
651:
650:
638:
635:
631:
625:
621:
617:
614:
594:
589:
585:
579:
575:
571:
568:
547:, so it is an
536:
531:
527:
522:
518:
515:
512:
490:
487:
483:
479:
476:
473:
470:
450:
430:
427:
422:
419:
415:
411:
408:
382:
348:
345:
343:
340:
321:
317:
280:
276:
270:
266:
262:
231:
227:
223:
183:
179:
151:
144:
129:
122:
115:
108:
93:for different
89:
78:
59:
53:
46:
15:
13:
10:
9:
6:
4:
3:
2:
2524:
2513:
2510:
2509:
2507:
2492:
2489:
2487:
2484:
2483:
2481:
2477:
2471:
2468:
2466:
2463:
2461:
2458:
2456:
2453:
2451:
2448:
2447:
2445:
2441:
2435:
2432:
2430:
2427:
2425:
2422:
2420:
2417:
2416:
2414:
2410:
2404:
2401:
2399:
2396:
2394:
2391:
2389:
2386:
2385:
2383:
2379:
2374:
2367:
2362:
2360:
2355:
2353:
2348:
2347:
2344:
2334:
2330:
2325:
2320:
2316:
2312:
2305:
2302:
2297:
2293:
2288:
2283:
2279:
2275:
2271:
2267:
2263:
2256:
2253:
2248:
2244:
2240:
2236:
2232:
2228:
2224:
2217:
2214:
2209:
2205:
2201:
2197:
2193:
2189:
2185:
2178:
2175:
2170:
2166:
2162:
2158:
2154:
2150:
2146:
2142:
2138:
2131:
2129:
2125:
2120:
2116:
2112:
2108:
2104:
2100:
2096:
2092:
2088:
2084:
2077:
2074:
2069:
2065:
2061:
2057:
2053:
2049:
2045:
2038:
2035:
2030:
2026:
2022:
2018:
2013:
2008:
2004:
2000:
1996:
1989:
1986:
1981:
1977:
1973:
1969:
1964:
1959:
1955:
1951:
1947:
1940:
1937:
1932:
1928:
1924:
1920:
1916:
1912:
1905:
1902:
1897:
1893:
1889:
1885:
1881:
1877:
1872:
1867:
1863:
1859:
1855:
1848:
1845:
1840:
1836:
1832:
1828:
1824:
1820:
1816:
1812:
1808:
1801:
1798:
1793:
1789:
1785:
1781:
1776:
1771:
1767:
1763:
1759:
1752:
1750:
1746:
1740:
1736:
1733:
1732:
1728:
1726:
1724:
1720:
1715:
1713:
1709:
1701:
1699:
1679:
1671:
1659:
1655:
1645:Special cases
1644:
1642:
1635:
1631:
1612:
1609:
1606:
1600:
1595:
1592:
1589:
1585:
1577:
1575:
1571:
1555:
1552:
1547:
1544:
1541:
1537:
1528:
1520:
1516:
1512:
1509:
1506:
1503:
1500:
1497:
1493:
1487:
1482:
1479:
1476:
1472:
1464:
1462:
1458:
1442:
1439:
1434:
1431:
1428:
1424:
1415:
1407:
1403:
1399:
1396:
1392:
1384:
1383:
1382:
1380:
1376:
1358:
1355:
1352:
1348:
1339:
1335:
1328:
1324:
1320:
1316:
1312:
1305:
1301:
1300:configuration
1297:
1293:
1289:
1285:
1280:
1279:
1272:
1268:
1249:
1246:
1243:
1237:
1232:
1229:
1226:
1222:
1214:
1212:
1208:
1192:
1189:
1184:
1181:
1178:
1174:
1170:
1165:
1162:
1159:
1155:
1149:
1144:
1141:
1138:
1134:
1126:
1124:
1120:
1104:
1101:
1096:
1093:
1090:
1086:
1080:
1075:
1072:
1069:
1065:
1057:
1056:
1055:
1053:
1049:
1031:
1028:
1025:
1021:
1012:
1005:
1001:
993:
991:
989:
988:
983:
979:
972:
966:
958:
956:
954:
950:
942:
940:
924:
920:
914:
910:
906:
899:
883:
879:
868:
863:
861:
857:
854:
850:
846:
842:
821:
817:
811:
807:
803:
796:
792:
787:
785:
767:
763:
759:
752:
748:
724:
720:
716:
711:
707:
703:
691:
679:
677:
675:
671:
667:
663:
658:
655:
633:
629:
623:
619:
612:
587:
583:
577:
573:
566:
558:
554:
550:
529:
525:
520:
516:
510:
488:
485:
481:
477:
474:
471:
468:
448:
425:
420:
417:
413:
406:
398:
394:
390:
386:
383:
380:
376:
372:
371:
370:
368:
364:
362:
358:
354:
346:
341:
339:
337:
315:
307:
303:
299:
294:
278:
274:
268:
264:
260:
253:
249:
248:
229:
225:
221:
214:
210:
206:
202:
197:
177:
169:
165:
161:
156:
154:
147:
140:
136:
132:
125:
118:
111:
104:
100:
96:
92:
85:
81:
74:
70:
66:
62:
52:
45:
41:
37:
33:
29:
25:
21:
2402:
2314:
2310:
2304:
2269:
2265:
2255:
2230:
2226:
2216:
2191:
2187:
2177:
2144:
2140:
2094:
2090:
2076:
2051:
2047:
2037:
2002:
1998:
1988:
1953:
1949:
1939:
1917:(2): 41–52.
1914:
1910:
1904:
1861:
1857:
1847:
1814:
1810:
1800:
1765:
1761:
1716:
1705:
1661:
1657:
1650:
1648:
1639:
1633:
1629:
1573:
1569:
1460:
1456:
1378:
1374:
1337:
1330:
1326:
1322:
1318:
1314:
1307:
1306:. Denote by
1303:
1302:for machine
1299:
1295:
1291:
1287:
1281:
1278:
1276:
1270:
1266:
1210:
1206:
1122:
1118:
1051:
1047:
1007:
1003:
999:
997:
985:
981:
974:
970:
968:
952:
948:
946:
870:
864:
856:
848:
844:
837:
794:
790:
788:
783:
750:
746:
683:
662:local search
659:
656:
652:
556:
552:
396:
392:
388:
378:
367:
365:
356:
352:
350:
305:
301:
297:
295:
251:
245:
212:
208:
204:
200:
198:
167:
163:
157:
149:
142:
134:
127:
120:
113:
106:
98:
94:
87:
83:
76:
72:
64:
57:
50:
43:
39:
19:
18:
2287:10251/35412
982:egalitarian
749:machines,
666:tabu search
369:presented:
141:- in which
105:- in which
82:. The term
2470:Throughput
1741:References
1702:Extensions
1628:for every
1265:for every
342:Algorithms
2465:Tardiness
2455:Earliness
2429:Flow shop
2424:Open shop
2319:CiteSeerX
2296:0377-2217
2247:0736-5845
2208:0377-2217
2169:206799898
2161:1436-4646
2111:0004-5411
2068:0895-4801
2021:0004-5411
1972:0001-0782
1931:0895-7177
1896:254694965
1888:1094-6136
1871:1011.4957
1831:1436-4646
1784:0004-5411
1601:∈
1572:in 1,...,
1513:∈
1501:∋
1494:∑
1473:∑
1459:in 1,...,
1400:∈
1393:∑
1238:∈
1209:in 1,...,
1190:≤
1171:⋅
1135:∑
1121:in 1,...,
1066:∑
907:∑
849:identical
804:∑
760:∑
747:unrelated
634:ϵ
557:unrelated
526:ϵ
486:−
478:⋅
472:≥
469:ϵ
357:identical
261:∑
222:∑
84:unrelated
2506:Category
2460:Lateness
2450:Makespan
2434:Job shop
2375:problems
2119:12329294
2029:10956951
1839:52867171
1792:18693114
1006:and job
441:, where
298:maximize
69:makespan
1980:2507557
836:(where
553:maximum
397:uniform
393:maximum
379:maximum
353:maximum
302:minimum
205:average
201:maximum
137:), and
126:(where
56:, ...,
2321:
2294:
2245:
2206:
2167:
2159:
2117:
2109:
2066:
2027:
2019:
1978:
1970:
1929:
1894:
1886:
1837:
1829:
1790:
1782:
949:profit
373:Exact
22:is an
2165:S2CID
2115:S2CID
2025:S2CID
1976:S2CID
1892:S2CID
1866:arXiv
1835:S2CID
1788:S2CID
549:FPTAS
42:jobs
2292:ISSN
2243:ISSN
2204:ISSN
2157:ISSN
2107:ISSN
2064:ISSN
2017:ISSN
1968:ISSN
1927:ISSN
1884:ISSN
1827:ISSN
1780:ISSN
1666:=1,M
784:jobs
668:and
300:the
97:and
30:and
2329:doi
2282:hdl
2274:doi
2270:211
2235:doi
2196:doi
2192:156
2149:doi
2099:doi
2056:doi
2007:doi
1958:doi
1919:doi
1876:doi
1819:doi
1770:doi
1725:).
1684:max
1662:P|p
1653:i,j
1377:is
1329:in
984:or
977:i,j
795:R||
751:R||
698:max
320:min
306:R||
252:R||
213:R||
182:max
168:R||
145:i,j
109:i,j
90:i,j
79:i,j
63:on
26:in
2508::
2327:.
2315:35
2313:.
2290:.
2280:.
2268:.
2264:.
2241:.
2231:18
2229:.
2225:.
2202:.
2186:.
2163:.
2155:.
2145:46
2143:.
2139:.
2127:^
2113:.
2105:.
2095:48
2093:.
2089:.
2062:.
2052:15
2050:.
2046:.
2023:.
2015:.
2003:23
2001:.
1997:.
1974:.
1966:.
1954:17
1952:.
1948:.
1925:.
1915:20
1913:.
1890:.
1882:.
1874:.
1862:17
1860:.
1856:.
1833:.
1825:.
1815:46
1813:.
1809:.
1786:.
1778:.
1766:23
1764:.
1760:.
1748:^
1714:.
1632:,
1574:n;
1461:m;
1269:,
1211:m;
1123:n;
990:.
939:.
871:R|
862:.
676:.
605:=
574:10
482:10
414:10
363:.
338:.
293:.
148:=
119:/
112:=
49:,
2365:e
2358:t
2351:v
2335:.
2331::
2298:.
2284::
2276::
2249:.
2237::
2210:.
2198::
2171:.
2151::
2121:.
2101::
2070:.
2058::
2031:.
2009::
1982:.
1960::
1933:.
1921::
1898:.
1878::
1868::
1841:.
1821::
1794:.
1772::
1680:C
1670:|
1668:j
1664:j
1651:p
1636:.
1634:j
1630:i
1616:}
1613:1
1610:,
1607:0
1604:{
1596:j
1593:,
1590:i
1586:x
1570:j
1556:1
1553:=
1548:c
1545:,
1542:i
1538:x
1532:)
1529:T
1526:(
1521:i
1517:C
1510:c
1507:,
1504:j
1498:c
1488:m
1483:1
1480:=
1477:i
1457:i
1443:1
1440:=
1435:c
1432:,
1429:i
1425:x
1419:)
1416:T
1413:(
1408:i
1404:C
1397:c
1379:c
1375:i
1359:c
1356:,
1353:i
1349:x
1338:T
1336:(
1333:i
1331:C
1327:c
1323:i
1319:i
1315:T
1313:(
1310:i
1308:C
1304:i
1296:T
1292:i
1288:i
1273:.
1271:j
1267:i
1253:}
1250:1
1247:,
1244:0
1241:{
1233:j
1230:,
1227:i
1223:z
1207:i
1193:T
1185:j
1182:,
1179:i
1175:p
1166:j
1163:,
1160:i
1156:z
1150:n
1145:1
1142:=
1139:j
1119:j
1105:1
1102:=
1097:j
1094:,
1091:i
1087:z
1081:m
1076:1
1073:=
1070:i
1052:j
1048:i
1032:j
1029:,
1026:i
1022:z
1010:,
1008:j
1004:i
975:p
971:i
953:ε
925:j
921:C
915:j
911:w
898:|
884:j
880:r
855:.
845:j
840:j
838:w
822:j
818:C
812:j
808:w
768:j
764:C
733:)
730:)
725:3
721:n
717:,
712:2
708:n
704:m
701:(
695:(
692:O
637:)
630:/
624:2
620:n
616:(
613:O
593:)
588:2
584:n
578:l
570:(
567:O
535:)
530:2
521:/
517:n
514:(
511:O
489:l
475:2
449:l
429:)
426:n
421:l
418:2
410:(
407:O
389:ε
316:C
279:i
275:C
269:i
265:w
230:i
226:C
209:n
178:C
164:R
152:i
150:p
143:p
135:j
130:j
128:s
123:j
121:s
116:i
114:p
107:p
99:j
95:i
88:p
77:p
73:i
65:m
60:n
58:J
54:2
51:J
47:1
44:J
40:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.