Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 28:
=== Minimizing the maximum completion time (makespan) ===
Minimizing the ''maximum'' completion time is NP-hard even for ''identical'' machines, by reduction from the [[partition problem]]. Many exact and approximation algorithms are known.
For ''identical'' machines, the problem is equivalent to [[multiway number partitioning]], where the job lengths are the numbers, the number of machines (denoted here by ''m'') is the number of parts (denoted there by ''k''), and the goal is to minimize the maximum sum. See [[multiway number partitioning#minmax]] for details about exact and approximate algorithms.
'''Graham''' proved that:
| |||