Effective Automation of Planning and Scheduling

This article was published in APICS Extra, Vol 4, No. 9, September 30, 2009 : Author Pankaj Mehta

Need for automation

A problem should be solved only once. If it has to be solved a second time then the solving should be automated. This rule is generally applied in all efficient organizations, particularly cost-conscious manufacturing organizations but paradoxically scheduling and planning problems continue to be solved over and over again. Why is it that enough is not done to automate the solution to this problem? Solutions to such problems come from the areas of Operations Research and Artificial Intelligence where practitioners have developed their own formal methodologies and vocabulary to the point that that body of knowledge is unintelligible to supply chain practitioners.

While standard, formal methodology and defensible results are important considerations for academics, supply chain practitioners look for ease of understanding, robustness and are comfortable with a satisficing approach, that is, for them a decision made quickly with available information is better than one that requires a lot more background information and processing time. In this article we provide an example of how planning and scheduling can be automated.

Modelling the problem

A scheduling problem can be stated as a Travelling Salesman problem: a salesman has to visit each and every town in a list but visit only once and the problem is to find an itinerary that will be minimise cost. Analogously, a scheduling problem is to find a sequence of jobs that can be run on a machine such that the overall time or cost is minimised. In Operations Research, integer-programming techniques are used to solve such problems. Linear programming solutions have also been successfully implemented. Scheduling can also be modelled as a state change problem; a machine-state being the job that has been scheduled to it and the problem is to determine a sequence of state-changes that would satisfy the objective of say minimum cost. A state-space search approach can be used to solve the problem. However, a strategy based on heuristics and amalgamation of standard algorithms is generally better understood and is hence more palatable to practitioners.

Paper Mill

We show here an application of heuristic techniques to simplify and automate the planning and scheduling problems at a paper mill. Let's call it XYZ. It is a small, fictional paper mill that manufactures a variety of papers and delivers it to its customers in the form of wound paper rolls or sheets cut to specified sizes. Paper is made by pulping wood, recycled paper and other fibres into a slurry which when dewatered over screens, pressed and dried, turns into the familiar product. It is primarily characterised by its weight per unit area (usually g/m² or gsm) and its colour and secondarily by its surface properties or other special attributes imparted through additives and coatings.

XYZ has a paper machine that can produce paper of different weights (gsm) and colours. We assume that pulp supply is unconstrained. The machine can be run at a certain maximum speed for a particular grade. If heavier grades are produced then the machine is to be slowed down to allow proper drainage and drying of paper to take place. In industry parlance the machine operation is dryer limited.

Papermaking is a continuous process. If the type of paper grade is to be changed the pulp, dye and additive flow rates have to be gradually changed till the right product properties are achieved. The paper produced between any two grades of paper is of indeterminate quality and is generally a waste. The bigger the difference between grades the more is the waste. In some cases the machine has to be stopped, washed up and all holding tanks emptied and cleaned before a new grade is started. That is why paper makers prefer to gradually step through grammage and colour changes.

The paper coming off the paper machine is reeled on a steel spool and is not in a deliverable form. Customers want paper in the form of rolls of specific diameter and width. This is done by unwinding the parent reel, slitting it to specified widths and winding individual webs onto cardboard cores to produce customer paper rolls. The buffer between the paper machine and the winder is small and the two can generally be treated as tightly coupled machines. The buffer only serves to decouple the machines long enough to overcome minor maintenance down time. Wastage can occur at the winder if the sum of widths of rolls does not add up to the width of the parent reel.

XYZ also supplies paper in sheet form. The customers specify the sheet size and the mill first produces paper rolls to suit the required paper width. Multiple rolls of paper are unwound at the sheeter and are cut to required length in a batch process. The sheeter has limitations on the number of rolls it can use at the one time, the total grammage of paper that its knife can handle and the speed at which it can run. The sheets are automatically stacked on a pallet and delivered to the customer after further packing.

Business imperative

XYZ manufactures on demand against specific orders and also makes to stock based on time-phased list of requirements generated by a manufacturing resource planning process. These business processes are stable and may be assumed to be optimal. Based on these inputs a simple, feasible schedule can always be created but such a schedule will generally be sub-optimal, characterised by jobs being late or early or forcing excessive changeovers. Every business needs to take a balanced view and work to a schedule that minimises costs and not one that only reduces tardiness.

The consequences of an order being late vary and depend on the amount of delay. For short delays the liability may be limited to paying liquidated damages but excessive delays can lead to cancellation and payment of damages. Therefore, the cost of delay should be computed using a polynomial function of at least degree two so that the bias is towards reducing delays. On the other hand, manufacturing too early would result in blocking of working capital and increase in warehousing costs. Such costs can be modelled as a linear function of delay.

It is the sequence dependent changeover time that is critical to the scheduling process. In general, the changeover time for the sheeter can be modelled as a function of length and width changes and the paper machine changeover modelled as a function of changes in grammage, colour and composition.

The overall cost function is therefore made up of a) cost of delay, b) cost of haste and c) cost of changeover.

Scheduling

As a first step the sheeter jobs can be lined up in the sequence of the latest delivery dates. They are then the sequence: J1, J2, J3,…, JN-1, JN

Looking at possible improvements to the schedule we can check the consequences of swapping positions of job Jm and Jn. Jm might get delayed and suffer a penalty for being late but it may be better off in respect of sequence dependent penalty and overall we might be better off. On the other hand Jn having been brought forward might suffer a penalty for haste and will have a change in changeover cost. The changeover costs for Jm+1 and Jn+1 will change as their predecessors would have changed. In addition all jobs from Jm+1 to Jn-1 will have changed timings and consequently have a different late/haste penalty. If there is an overall saving in cost by swapping Jm and Jn then make the swap, otherwise not. This process would be repeated for Jm+1 and subsequent jobs.

Already the order of complexity of this algorithm is beginning to look rather high. But we do not need to swap all jobs. By delaying a job we can at most save all of the changeover cost but will continue to incur penalty for delay. The point at which the penalty for delay exceeds the changeover cost is the cut off point. There is no point in testing beyond this limit. Before commencing trials we look at the maximum delay that can be tolerated and restrict search up to the job whose completion time is within the acceptable limit.

Next similar scheduling would be carried out for the paper machine. Having done so we would realise that some jobs on the paper machine have been scheduled later than the latest start time of corresponding job on the sheeter. Knowing that the paper machine is critical to operations and its cost of operation is far in excess of the sheeter we simply look at the affected jobs on the sheeter and assign them a start time that is no earlier than the completion of corresponding job on the paper machine. These jobs also get flagged as ones that may not be moved forward. All that now needs to be done is to rerun the sheeter algorithm but this time around ignore jobs that cannot be brought forward. As a result the revised sheeter schedule might have gaps in it but this idle time would be acceptable trade off.

Conclusion

Reflecting on above, we have an algorithm that is rooted in common sense and which does not require complicated modelling. It is efficient to run because by applying business rules we have reduced the search space and likewise reduced iterations by recognising the relative importance of machines. The final schedule is generated automatically based solely on sales and MRP orders and is close to optimal for the business.

The application of automated planning and scheduling is by no means limited to the paper industry. The technique outlined above can be adapted to almost any industry provided that sufficient thought is given first to business conditions, needs and workable rules of thumb elicited to ensure optimal performance. Adapted and customised solutions are indeed attractive alternatives to ”one size fits all” solutions.