22:
589:
532:
479:
139:
There is a complex project that is composed of several sub-tasks. We would like to assign tasks to workers, such that the project finishes in the shortest possible time. As an example, suppose the "project" is to feed the goats. There are three goats to feed, one child can only feed one goat at a
126:
of a project is the length of time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project schedule, by efficiently using project resources, adding the lowest number of additional
222:
Fair makespan minimization - When assigning tasks to agents, it is required both to minimize the makespan, and to avoid envy. If the fastest worker is given a job, he has to be compensated for his extra effort.
140:
time, and there are two children that can feed them: Shmuel feeds each goat in 10 minutes and Shifra feeds each goat in 12 minutes. Several schedules are possible:
331:
150:
If we let Shifra feed two goats and Shmuel one goat, then the makespan is 24 (2×12 for Shifra, 10 for Samuel working beside and in parallel to Shifra);
147:
If we let Shifra feed one goat and Shmuel two goats, then the makespan is 20 (2×10 for Shmuel, 12 for Shifra working beside and in parallel to Shmuel);
573:
516:
630:
324:
105:
659:
649:
43:
370:
360:
317:
86:
566:
365:
58:
664:
191:
identical stations. Each job should be executed on a single station. This is usually regarded as an online problem.
32:
355:
247:"A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption"
39:
65:
654:
509:
386:
623:
458:
227:
presents a general framework for optimization problems with envy-freeness guarantee using monetary payments.
559:
432:
422:
340:
128:
72:
427:
396:
391:
208:
194:
177:
different stations. Consider using this rule to sequence jobs that must go through both work centers.
54:
502:
453:
401:
180:
127:
resources as possible to achieve the minimum makespan. The term commonly appears in the context of
119:
616:
437:
268:
219:
different stations. Each job should spend some time at each station, in a pre-determined order.
166:
600:
543:
486:
539:
295:
258:
153:
If we let Shifra feed all goats, then the makespan is 36 (3×12 for Shifra, 0 for Shmuel).
144:
If we let Shmuel feed all goats, then the makespan is 30 (3×10 for Shmuel, 0 for Shifra);
79:
643:
205:
different stations. Each job should spend some time at each station, in a free order.
272:
309:
157:
So in this case, the second schedule attains the shortest makespan, which is 20.
596:
21:
299:
263:
246:
588:
531:
286:
Mu'alem A (2014). "Fair by design: Multidimensional envy-free mechanisms".
478:
313:
15:
604:
547:
490:
446:
410:
379:
348:
46:. Unsourced material may be challenged and removed.
624:
567:
510:
325:
8:
631:
617:
574:
560:
517:
503:
332:
318:
310:
262:
106:Learn how and when to remove this message
237:
161:Types of makespan minimization problems
7:
585:
583:
528:
526:
475:
473:
44:adding citations to reliable sources
603:. You can help Knowledge (XXG) by
546:. You can help Knowledge (XXG) by
489:. You can help Knowledge (XXG) by
14:
251:Applied Computing and Informatics
587:
530:
477:
245:Afshar-Nadjafi, Behrouz (2018).
20:
31:needs additional citations for
1:
485:This computing article is a
288:Games and Economic Behavior
681:
582:
525:
472:
300:10.1016/j.geb.2014.08.001
264:10.1016/j.aci.2014.02.003
459:Truthful job scheduling
411:Optimization objectives
660:Computer science stubs
650:Scheduling (computing)
599:-related article is a
341:Optimal job scheduling
209:Flow shop scheduling
195:Open-shop scheduling
40:improve this article
454:Interval scheduling
181:Job shop scheduling
120:operations research
447:Other requirements
371:Unrelated machines
361:Identical machines
665:Mathematics stubs
612:
611:
555:
554:
498:
497:
467:
466:
116:
115:
108:
90:
672:
633:
626:
619:
591:
584:
576:
569:
562:
540:computer science
534:
527:
519:
512:
505:
481:
474:
380:Multi-stage jobs
366:Uniform machines
334:
327:
320:
311:
304:
303:
283:
277:
276:
266:
242:
111:
104:
100:
97:
91:
89:
48:
24:
16:
680:
679:
675:
674:
673:
671:
670:
669:
655:Computing stubs
640:
639:
638:
637:
581:
580:
524:
523:
470:
468:
463:
442:
406:
375:
344:
338:
308:
307:
285:
284:
280:
244:
243:
239:
234:
163:
137:
112:
101:
95:
92:
49:
47:
37:
25:
12:
11:
5:
678:
676:
668:
667:
662:
657:
652:
642:
641:
636:
635:
628:
621:
613:
610:
609:
592:
579:
578:
571:
564:
556:
553:
552:
535:
522:
521:
514:
507:
499:
496:
495:
482:
465:
464:
462:
461:
456:
450:
448:
444:
443:
441:
440:
435:
430:
425:
420:
414:
412:
408:
407:
405:
404:
399:
394:
389:
387:Parallel tasks
383:
381:
377:
376:
374:
373:
368:
363:
358:
356:Single machine
352:
350:
349:One-stage jobs
346:
345:
339:
337:
336:
329:
322:
314:
306:
305:
278:
257:(2): 192–201.
236:
235:
233:
230:
229:
228:
220:
206:
192:
178:
167:Johnson's Rule
162:
159:
155:
154:
151:
148:
145:
136:
133:
114:
113:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
677:
666:
663:
661:
658:
656:
653:
651:
648:
647:
645:
634:
629:
627:
622:
620:
615:
614:
608:
606:
602:
598:
593:
590:
586:
577:
572:
570:
565:
563:
558:
557:
551:
549:
545:
542:article is a
541:
536:
533:
529:
520:
515:
513:
508:
506:
501:
500:
494:
492:
488:
483:
480:
476:
471:
460:
457:
455:
452:
451:
449:
445:
439:
436:
434:
431:
429:
426:
424:
421:
419:
416:
415:
413:
409:
403:
400:
398:
395:
393:
390:
388:
385:
384:
382:
378:
372:
369:
367:
364:
362:
359:
357:
354:
353:
351:
347:
342:
335:
330:
328:
323:
321:
316:
315:
312:
301:
297:
293:
289:
282:
279:
274:
270:
265:
260:
256:
252:
248:
241:
238:
231:
226:
221:
218:
214:
210:
207:
204:
200:
196:
193:
190:
186:
182:
179:
176:
172:
168:
165:
164:
160:
158:
152:
149:
146:
143:
142:
141:
134:
132:
130:
125:
121:
110:
107:
99:
88:
85:
81:
78:
74:
71:
67:
64:
60:
57: –
56:
52:
51:Find sources:
45:
41:
35:
34:
29:This article
27:
23:
18:
17:
605:expanding it
594:
548:expanding it
537:
491:expanding it
484:
469:
417:
291:
287:
281:
254:
250:
240:
224:
216:
212:
211:– there are
202:
198:
197:– there are
188:
184:
183:– there are
174:
170:
169:– there are
156:
138:
123:
117:
102:
93:
83:
76:
69:
62:
50:
38:Please help
33:verification
30:
597:mathematics
644:Categories
438:Throughput
232:References
129:scheduling
66:newspapers
55:"Makespan"
433:Tardiness
423:Earliness
397:Flow shop
392:Open shop
294:: 29–46.
215:jobs and
201:jobs and
187:jobs and
173:jobs and
96:June 2019
428:Lateness
418:Makespan
402:Job shop
343:problems
273:62145189
124:makespan
225:Mu'alem
135:Example
80:scholar
271:
122:, the
82:
75:
68:
61:
53:
595:This
538:This
269:S2CID
87:JSTOR
73:books
601:stub
544:stub
487:stub
59:news
296:doi
259:doi
118:In
42:by
646::
292:88
290:.
267:.
255:14
253:.
249:.
131:.
632:e
625:t
618:v
607:.
575:e
568:t
561:v
550:.
518:e
511:t
504:v
493:.
333:e
326:t
319:v
302:.
298::
275:.
261::
217:m
213:n
203:m
199:n
189:m
185:n
175:2
171:n
109:)
103:(
98:)
94:(
84:·
77:·
70:·
63:·
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
