Introduction

For years spreadsheets have been used to design and prototype scheduling systems. They have now grown up, and are being used to develop serious production scheduling applications. A comprehensive tutorial available at no charge at www.production-scheduling.com and this paper summarizes it, introduces some of the concepts, and illustrates what is possible with a spreadsheet.

Background

I have designed, built and implemented production scheduling systems for manufacturing companies for over 11 years. When PC's and spreadsheets were less capable than they are now, we used spreadsheets to design and prototype scheduling algorithms, and to train on some of the principles of scheduling. Prototype designs were then handed over to software developers to write in more resilient and efficient programming languages.

Impatient clients pressured us to throw several thousand records of data at the prototypes and use them for live scheduling, before handing them to the software developers. So, in order to 'shoehorn' a big scheduling task into a small PC, we recorded macros that wrote a formula, copied it down, overwrote the cells with values, then moved on to the next column, so that no memory consuming live formulas were left behind. Typically, most of the macro code prepared downloaded data for scheduling, and generated reports from the schedule, with only a small portion of the macro calculating the schedule itself. We ended up with big cumbersome macro driven scheduling systems that locks out ordinary, spreadsheet literate people.

Thankfully we now have Pentium III's which will handle large amounts of data, and have features such as Excel's PivotTable which will re-arrange and summarize data for scheduling, and prepare reports without writing macros. It makes the job, of building a scheduling system with a spreadsheet, a whole lot easier, and within the capability of the average spreadsheet user.

Top

The Case for Spreadsheets

There is a worldwide shortage of IT and programming skills, but in most businesses a good depth of spreadsheet literacy has developed. With some assistance, manufacturers can harness these skills, uplift them, and end up with user- maintainable production scheduling systems. The cost is considerably less than implementing one of the scheduling packages, and the risk of being stranded without IT support, is lower. It must be recognized, however that spreadsheets may be good for manipulating data, but they are not transaction processors, and it is wise to interface to a host ERP system.

Structured and Disciplined Approach

Spreadsheets have earned themselves a bad reputation amongst software purists, because they can, and often are, used in an unstructured way. Building a scheduling system requires a structured and disciplined approach. Please resist the trap, that many fall into, of creating a table on a single worksheet that looks like the report that you want to see. The approach used here is to create lists in the form of databases, with a heading at the top of each column, and with universal formulas that can be copied and pasted down a column, and work on every row. If all the calculations are done in a structured database, then reports, with sub-totals and charts, can easily be created with a PivotTable.

Top

Time Cascades Downwards

Re-sequencing the Schedule

Top

A Simple Gantt Chart

The mistake that many people make when constructing a spreadsheet based schedule, is to start by making a Gantt chart with time running from left to right. The technique here is to recognize that a Gantt chart is merely a report that represents time in buckets, whereas the calculations run downwards and are bucketless.

The formula in each cell of the Gantt chart looks up at the top row, and flags the cell if it lies between the stop and start of the job, and conditional formatting is used to color it. The size of the bucket is variable, for example:

Top

Change-over Matrix

Often change-over time can be saved by undertaking jobs in a certain sequence. A typical example would be a paint line where a change from a dark color to a light color requires a much longer cleaning process than from a light color to a dark color. The differential change over times are expressed in the matrix to the left, and the schedule on the right has an extra column for change-overs (C/O).

It is assumed that the first job has already been set up, so has a change-over time of zero. Now re-sequencing the schedule becomes a little more challenging. The above sequence would mean that 3 jobs would be late and 3.5 hours would be spent on change-overs, so let us see if we can sequence more intelligently:

Top

Base 1900 Date

Top

Working With a Calendar

Our simple schedule assumes that we work 24 hours a day for 7 days per week, which is fine if we are scheduling a continuous process such as an oil refinery or a paper mill, but most manufacturers work to a shift calendar. Here is an example of a shift calendar:

Each row of the calendar is a working period, and the "Cum. Days" column tracks the cumulative days from the beginning of the calendar. The calculations to the right of the calendar assume that we start a job at 12:27pm on 4 June and work for 22.8 hours, when will the job stop? There are a series of formulas that reference the calendar and calculate the stop time, and the detailed derivation of the formulas is set out in the tutorial. Broadly the formulas work in this way: The job starts during the working period on row 7, 0.175 days from the start of the calendar, and the job will stop during row 17 of the calendar at 11:15am on 6 June.

This is an example of how the schedule looks when we work through the calendar:

Top

Jobs That Pass Through Multiple Work Centers

So far the start of a job is determined by the stop of the previous job, but where a job goes through several operations on different work stations, a work station may have to wait for the job to emerge from the previous work station before it can start. Here is an example of Jobs A, B and C passing through work centers 6, 7 and 8:

Each operation looks up the stop time of the previous operation (if there is one), it also looks at the stop of the previous job on the work center, and uses the later of the two to establish the start time. Note the gaps where a work center has to wait.

A similar technique is used when two or more manufactured components meet at an assembly operation. A separate column is set up for each component, and the stop dates determine the start of the assembly operation.

Notice also that the Gantt chart buckets are 8 hour periods labeled with a base 1900 date and time, and that instead of simple flags, the buckets show the number of job hours in each bucket. The Gantt chart formula is more involved than a simple flag, and a full explanation is in the tutorial.

Now is a good point to introduce some Theory of Constraints (TOC) thinking. Have a look at Job C going through work center 7. It starts at 11:00pm as soon as it comes off work center 6, runs till 5:00am, then waits for 4 hours for work center 8 to become available. Why start it earlier than you have to, and have it lying in WIP?

Top

Push-Pull-Push 3 Pass Logic

In Eli Goldratt's book, The Haystack Syndrome, he describes a scheduling technique which he likens to "leveling the ruins" with a bulldozer in 3 passes, forwards, backwards, and forwards again. A very similar 3 pass algorithm can be done with a spreadsheet. The details of the calculations are set out in the tutorial, but in essence this is how it works. There are two jobs on the same work center, one due in 24 hours time and the other in 48 hours:

Day 1 Day 2   Jobs Hours Due 0  8  16 24 32 40 48 56   PUSH      Job A 32 24                 Job B 8 48                   PULL      Job A 32 24                 Job B 8 48                   PUSH AGAIN      Job A 32 24                 Job B 8 48

The first pass starts now and does both jobs as soon as possible The second pass starts each job just in time to meet the due date. Job A will have to have started yesterday. Obviously, this is not possible. The third pass pushes Job A to a feasible start time, and leaves Job B where it was, to leave a schedule which is the best due date performance that can be achieved, but with a "pull" approach. When the algorithm is applied to a multiple work center schedule, it has the effect of delaying an operation until the next operation is ready for it, discouraging the building of WIP for the sake of keeping machines busy. The second pass works backwards, with the calculations going up the columns instead of down, and each operation may be influenced by the start of the next operation.

Top

Repetitive Production and Transfer Batches

Up to now our examples have been of jobs with a duration in hours. Here is an example of repetitive production, each job being for batches of multiple products that run through each work center at a rate per hour. First let us assume that the entire batch must be complete at a work center before it can go to the next work center.

Now see the impact of transferring products between work centers in batches of 10. What took 4 days, now takes less than 3 days:

If a fast operation follows a slow operation, as in this example, it will stop and start as it waits for each transfer batch to reach it. The 3 pass algorithm avoids this by delaying the start of the fast operation so that it catches up with the slow operation by the time the job finishes. To ensure that the second operation does not finish before the first, it needs to look up the stop, as well as the start of the previous operation. For simplicity these detailed calculations are hidden in this example, but they are explained in the tutorial.

Notice that the Gantt chart now shows the number of units produced in each time bucket. This is done by taking the hours per bucket, as in the previous Gantt chart, and multiplying by a rate per hour.

Top

Sequencing a Multiple Work Center Schedule

These simple examples show each product with the same routing, work center 6 then 7 then 8. Some processes work this way, so sequencing may simply be a matter or sorting operations by due date within work center. Manufacturing processes where the products follow very different routings, may require more sophisticated sequencing rules to be calculated. One such calculation works as follows:

• the loading on each work center, in hours, is calculated
• for each job the most heavily loaded work center that it passes through, is identified
• we consider this to be the job's constraint
• assuming infinite capacity (for now) we calculate the latest time that the job must start on the constraint, in order to meet its due date
• we then sort by this date to determine the sequence through each work center

Often it is a good idea to allow the sequences to be overridden manually to see how the schedule responds to changes in sequence.

Top

Putting it All Together

In my experience of several hundred scheduling systems, each one is different, but a typical spreadsheet scheduling system may have the following features:

• ODBC interfaces with a host ERP or MRP system
• routings through multiple work centers
• a BOM with several manufactured components at an assembly operation
• a separate calendar for each work center
• a change-over matrix for each work center
• repetitive production
• different transfer batch sizes for each product between each work center
• demand that may explode into several thousand operations
• a rough pre-schedule to establish a sequence for each operation
• the push-pull-push 3 pass algorithm
• Gantt charts with variable sized time buckets

The flow of data through the system would typically be as follows:

Such a system would:

• have about 20 pages in a workbook
• be up to 30Mb in size
• have finite scheduling calculations with up to 150 columns and several thousand rows
• contain about 10 PivotTables
• have NO macro code
• take from 5 to 30 seconds to re-schedule