Quick Survey of Production Scheduling Heuristics – Part 1

In my last post, I outlined three fundamental principles for selecting an approach to manufacturing scheduling.  The method that you select should be based on those three fundamental principles.  In this and next week’s posts, I will give you a quick survey of approaches for scheduling. 

For Job Shops

In a job shop, your primary need may be to schedule individual work centers or machines.  In this case, the following approaches should probably be considered:

  • Purely Due Date Driven Rules, including the following:
    • Earliest Due Date (EDD)
    • MST – Minimum slack time – where slack time is the difference between the time until the due date and the remaining processing time.
    • ODD – Operation due date – operation due dates are created that serve as intermediate deadlines prior to the real due date.
    • S/OPN – Slack time per operation – Choose the job with the smallest ratio between slack time and the number of operations remaining.
    • A/OPN – Allowance per operation – Prioritize the job with the smallest ratio between the “allowance” (time between the current date and the due date) and the number of remaining operations.
    • MOD – Modified operation due date – a modified operation due date is the larger of its original operation due date and its earliest possible finish time
    • COVERT—COVERT stands for “C over T”, where C represents the delay cost for the job and T represents the processing time for this operation.  Jobs are sequenced according to the ration of delay cost to processing time.
  • First-come, first serve (FCFS)
  • Shortest Processing Time (SPT)
  • CR by itself

Even though it ignores due dates, research shows that SPT tends to outperform or perform very well whether the goal is minimizing average job lateness,  # of jobs late, mean flow time, or WIP.   Some other variations of SPT include the following:

  • SPT with Critical Ratio (CR – time till due date divided by time to complete the order)
  • Shortest weighted processing time (SWPT – SPT weighted by a factor such as expected profit)
  • Truncated SPT (TSPT) – imposes a time limit on jobs in the queue where any jobs exceeding the limit are sequenced according to FCFS
  • Relief SPT (RSPT) employs FCFS until the queue length hits a specified value at which point the rule switches to SPT.

If you need to schedule multiple machines or work centers, then you may want to consider these heuristics:

  • Work in next queue (WINQ) – assigns highest priority to the job that will join the queue (after the current operation is completed) with the smallest workload (where workload is the sum of processing times waiting in that queue)
  • Expected Work in Next Queue (EWINQ) – similar to WINQ, except that it also accounts for jobs that are expected to arrive in the subsequent queue

Bottleneck Operations 

A bottleneck can occur within any type of manufacturing, including a job shop, repetitive manufacturing, or batch manufacturing.  In a job shop, it can often move from one resource or work center to another, depending on the mix of products demanded.  When there is a significant bottleneck, it is important to maximize throughput at the bottleneck operation, while keeping work-in-process (WIP) buffers under control.  The late Eli Goldratt devised the “Theory of Constraints” (TOC) in which the goal is to keep the constraint busy, leveraging buffers before the constraint and synchronizing the release of work to the shop floor to keep the buffer constant.  A related, but somewhat more transparent heuristic is called “Constant Work-in-Process” (CONWIP).  Some research has indicated that CONWIP can achieve lower work-in-process inventories than a full Kanban system.  In my next post, I’ll touch on repetitive make-to-stock manufacturing, network routing challenges, optimization, and how to evaluate and select the best approach.

I’m always grateful you took the time to read Supply Chain Action, and I’m delighted if you found something you can use.

On this Memorial Day weekend, remember the words of Edmund Burke, “All that is necessary for the triumph of evil is that good men do nothing.”

If you are in the USA, have a good Memorial Day holiday.  If not, have a wonderful weekend!

Acknowledgement:  Inventory Management and Production Planning and Scheduling, Silver, Pike and Peterson


About Arnold Mark Wells
Industry, software, and consulting background. I help companies do the things about which I write. If you think it might make sense to explore one of these topics for your organization, I would be delighted to hear from you. I am employed by Opalytics.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: