This is our first of many articles on production scheduling topics. Check out The Ondema Guide to Production Scheduling for an actionable resource to add to your tool chest.
What is makespan?
Makespan, in the context of operations research, is simply the amount of time between the start and completion of work.
In manufacturing and, more specifically, the context of production scheduling, makespan is equivalent to the completion time of the last job to leave the system (Pinedo, 2016). At a high level, the goal of production scheduling is to minimize makespan while efficiently using available manufacturing resources and avoiding additional resources.
Makespan...with Super Cobras
Our factory needs to produce three AH-1W Super Cobras because they are and will forever be the meanest, most beautiful thing to ever terrorize the skies 💥🚁. There are two US Marines that can assemble them and each Marine can only build one at a time. LtGen Puller can assemble a AH-1W in six hours. Sgt Daly can build one in five hours because we all know officers are inefficient and enlisted Marines get the real work done. With no other elements in the example we have the scheduling scenarios below:
- If LtGen Puller assembles all the AH-1Ws and Sgt Daly assembles none, the makespan is 18 hours (3 AH-1Ws x 6 hours each).
- It Sgt Daly assembles all the AH-1Ws and LtGen Puller assembles none, the makespan is 15 hours (3 AH-1Ws x 5 hours each).
- If LtGen Puller assembles one AH-1W and Sgt Daly assembles two, the makespan is 10 hours (1 x 6 for Puller, 2 x 5 for Daly working in parallel).
- If LtGen Puller assembles two AH-1Ws and Sgt Daly assembles one, the makespan is 12 hours (2 x 6 for Puller, 1 x 5 for Daly working in parallel).
With the goal of minimizing makespan, we select production schedule #3.
Let's look at another example in practice before diving into a super intense method of tackling the Job Shop Scheduling Problem (JSSP).
Calculating makespan on two machines
Production often involves the use of two or more machines to complete the required jobs, with varied time per job on each machine. Calculating makespan means finding the sequence of jobs that minimizes the time required to complete them.
Johnson's Rule, also known as an SPT(1)-LPT(2) schedule for those familiar with priority sequencing rules, is a method for scheduling jobs to minimize makespan with two machines or work centers. The basic steps are:
- List the jobs and the time required on each machine.
- Select the job with the shortest time. If that time is associated with the first machine, then schedule the job first. If that time is associated with the second machine then schedule the job last. Break ties arbitrarily.
- Remove the shortest job from further consideration.
- Repeat steps 2 and 3, working towards the center of the job schedule until no jobs remain.
Consider the list of jobs below (assembling AH-1W Super Cobras, of course 💥🚁) with the time required in hours on each machine:
- The shortest time is for J2 on M2 with 1.9 hours. Schedule this job last and remove it from further consideration. The order of jobs is now ?, ?, ?, ?, J2.
- The shortest time remaining is for J4 on M2 with 2.3 hours. Schedule this job in the last available slot and remove it from further consideration. The order of jobs is now ?, ?, ?, J4, J2.
- The shortest time remaining is for J1 on M1 with 2.4 hours. Schedule this job first and remove it from further consideration. The order of jobs is now J1, ?, ?, J4, J2.
- The shortest time remaining is for J5 on M1 with 3.1 hours. Schedule this job in the first available slot and remove it from further consideration. The order of jobs is now J1, J5, ?, J4, J2.
- The only job left to consider is J3. The jobs should be processed in the order J1, J5, J3, J4, J2 and in the same order on both machines. This minimizes makespan.
Johnson's Rule only works with two machines or work centers. There are work-arounds, such as splitting all machines into groups small enough to use Johnson's Rule. With three or more machines, the possible number of sequences becomes NP-hard. Speaking of NP-hard...
Let's get weird!
Note: you know I love getting into the weeds with scheduling, so read on at your own risk. All of the below is adapted from Pinedo's Scheduling: Theory, Algorithms, and Systems (2016). If you've gotten this far, you should buy his book.
We can use a Mixed Integer Program (MIP) to minimize the makespan for a permutation flow shop with an arbitrary number of machines, i.e. Fm | prmu | Cmax.
Don't worry. Let's eat this elephant one bite at a time.
MIP just means that some of the decision variables have to be integers at the optimal solution. Production scheduling problems are described by the triplet α | β | γ where α is the machine environment, β is processing details and constraints, and γ is the criteria to minimize (for a comprehensive reference that includes these variables, download our Production Scheduling Guide). In Fm | prmu | Cmax above:
- Fm is notation for a flow shop machine environment. There are m machines in a series, and each job j is processed on each machine. Each job follows the same route. After finishing on one machine a job joins the queue for the next machine. Queues operate under the First In-First Out (FIFO) rule.
- prmu is notation for permutation, which is a constraint that may appear in a flow show. This implies that the order (or permutation) in which the jobs go through the first machine is maintained throughout the system.
- Cmax is notation for minimizing the longest completion time C for a single job in a set of jobs.
Next, let's define some variables:
- n is the number of jobs.
- m is the number of machines.
- pij is the processing time for job j on machine i. There's a whole world of job processing time models, FYI.
- xjk is a decision variable that equals 1 if job j is the kth job in the sequence and 0 otherwise.
- Iik denotes idle time on machine i between the processing of the jobs in the kth position and (k+1)th position.
- Wik denotes the waiting time of the job in the kth position in between machines i and i+1.
Still with me? Cool. Our MIP for minimizing makespan can be shown as:
which is subject to the following constraints:
What do the constraints above mean?
- Exactly one job has to be assigned to position k for any k.
- Job j has to be assigned to exactly one position.
- The decision variable xjk is related to physical constraints, which enforces the relationships between idle time variables and waiting time variables.
An example to bring this weirdness to a merciful end
Consider a flow shop with five jobs that will be processed on four machines subject to the following processing times (remember, pij is the processing time for job j on machine i).
Using the MIP from above, the objective becomes:
This formulation is subject to a series of constraints, because of course it's never easy. For example, the constraint corresponding to k = 2 (i.e., the second job in the sequence) and i = 3 (i.e., the third machine) is:
I32+4x13+4x23+3x33+4x43+x53+W33-W32-3x12-6x22-3x32-2x42-5x52-I42 = 0
If you take one thing away...
Past two machines, constructing a job shop production schedule to minimize makespan gets complicated, very quickly. That's why it's NP-hard. Thank heavens for computers so we don't have to do the math.
If you've read this far, you're a brave soul. I owe you a beer or two. Leave a comment and I'll follow through.