In manufacturing, production processes frequently require the use of two or more machines to complete production jobs. The time per job on each machine typically varies. When you have several jobs to complete, makespan is the total time needed to finish all of them. Calculating makespan means finding the sequence of jobs that will minimize the time required.
To determine the minimum makespan for a set of jobs requiring two machines, start by sorting the job times into two lists. The first list consists of times for machine 1 and the second list contains job times for machine 2. Go through both lists and find the shortest time in either list. If the shortest time is from list one, schedule this job first and remove it from both lists. If the shortest time comes from the second list, schedule it last. Again, remove the job from both lists. Repeat this sorting process until every job is scheduled. The job sequence produced has the minimum possible makespan.
When three or more machines are required, the possible sequences grow based on a rapid mathematical progression. It quickly becomes impossible to do the sorting manually or even with a computer. Manufacturers settle for a reasonably efficient makespan, rather than an optimum one. One way of doing this is to split the jobs and machines into groups small enough to calculate makespan for each group.
