Skip to content

Instantly share code, notes, and snippets.

@ah45

ah45/Capacity Planning Problem Definition.md

Created November 7, 2016 10:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save ah45/0bc76a89e399557e6d691b5a82408180 to your computer and use it in GitHub Desktop.
Save ah45/0bc76a89e399557e6d691b5a82408180 to your computer and use it in GitHub Desktop.
Download ZIP
Constraint Based Scheduling
Raw
Capacity Planning Problem Definition.md

Following on from a meeting with Simon, Ed, and Bryan. It seems like we’re trying to answer two questions:

  • Where are we overloaded?
  • What aren't we using? (That we should look to find or fit work to.)

Different contexts:

  • Managing current load

    • Always starts with released shop orders.
    • Would typically also include planned shop orders and requisitions.

    Asks questions like:

    • Which work centres are overloaded? When? How much?
    • What is the load? (Released orders, planned orders, reqs, etc.)
    • When can the load be re-scheduled on the same work center? (Can the load be pulled forward or pushed back? How much by?)
    • Can the load be moved to a different work center? Which? When? (Identify alternates by production line.)

    The trouble here is that the more questions you start asking the more you realize that you are duplicating the work of a finite scheduler. Ultimately that’s what the goal appears to be: manually finite schedule those areas of the infinite schedule that indicate a capacity constraint. Surely we should just invest our energy into getting a workable finite schedule instead?

    Wherever possible we should quantify the load in human terms such as days, weeks, "shifts", etc. and not merely in pure numbers of hours.

  • Planning for future load

    • Forecast based

Aspects:

  • Production lines
  • Customers
  • Projects
  • Standard Names?

Work Centers with Interesting Consumption Patterns

  • MC027
  • MC028
  • MC040
  • MC068
  • MC273

References

Raw
Thoughts on Scheduling and Capacity Planning.md

Thoughts On Scheduling and Capacity Planning

In all cases we can assume that we have n jobs to schedule across m (> 2) resources with multiple, sequential, operations utilizing different resources to perform per job.

As a rough guide we have ~150 resources (active internal work centers) and ~2000 shop orders with ~21000 operations to schedule. Slightly under half of those orders are planned (~900) but as at the time of writing account for only a third of the operations (~7000.)

There are an ~300 unconverted requisitions which could account for ~3200 more operations.

So, this is already a large dataset without the addition of multiple customer forecasts.

Infinite Scheduling

Generally quite simple. The only constraints are the sequence of operations per job, resource availability (non-working times), and the maximum number of hours per operation on each resource.

It’s also a task that is easy to parallelize as each job can be scheduled in isolation.

Both backward and forward scheduling are equally valid and can be mixed.

Different job sets can be easily, and commutatively, combined using standard aggregations.

The data is fairly static and there is minimal “churn” resulting from new loads (or changes to existing loads) as there is no interaction between jobs.

There is no definite requirement to re-schedule jobs due to the progress of time however it would almost certainly be useful to be able to both see which jobs are overdue (have operations scheduled in the past) and to forward schedule them (being advised of the new finish date.)

Additional data provides no real utility. This isn’t so much a scheduling algorithm as it is an aggregation. Details of alternative resources, for example, have far more utility when interpreting and acting upon the results of the schedule than they do during the scheduling process.

Outcomes

  • Overdue indication for jobs (when backward scheduling if an operation is scheduled earlier than the current date then there is no means of achieving the required date, likewise if forward scheduling and the order does not finish before the required date.)
  • Resource over subscription (at potentially varying levels of detail.)

Essentially all an infinite schedule will give you is a heat map of where your current scheduling results in resource over loading. This could be produced at varying levels of detail both in time (daily, weekly, etc.) and resource grouping (per work center, production line, department, etc.)

This can then be used to manually adjust the loading by either altering the assigned resources, changing the target dates, or modifying the characteristics of the load (run times, etc.)

Finite Scheduling

By far the harder of the two problems and generally considered to be a NP-Complete problem. Your results will always be an estimate and never an “optimal” solution.

Genetic Algorithms are particularly well suited to providing solutions and provide significant opportunity for parallelism. Constraint or Logic based programming also provide useful frameworks for writing scheduling algorithms.

Forward scheduling is by far the more sensible approach. Backward scheduling really doesn’t make a lot of sense.

Different job sets can’t be combined but must instead be layered: using the calculation of one set as an input/constraint for the calculation of another.

Most changes to the input data will require significant if not total recalculation. Something as simple as changing the resource assigned to an operation or its run time will have significant knock-on effects.

The result should be recalculated periodically in order to stay relevant. Once per day would probably be sufficient.

Finite scheduling is better suited to running against multiple constraints such as both machine and labour availability. If you are only interested in modeling a single set of constrained resources (i.e. work centers) then an infinite schedule satisfies the 80/20 rule and requires significantly less effort. However, as the number and complexity of constraints increases so does the complexity of the calculation and finite capacity scheduling ceases to be more complex and so becomes the better model (as it produces more “accurate” results than infinite scheduling.) I would argue that this point is crossed by simply including labour scheduling alongside work center scheduling.

Unsurprisingly then, finite scheduling benefits greatly from additional data that provides more specificity in the requirements and details of potential alternatives. The more data that is available to the algorithm the better the resulting schedule will be.

Outcomes

  • Easy to produce list of late orders.
  • Resource bottlenecks can be identified by average operation queue time.
  • Provides the ability to produce accurate “best end dates” for new requirements (due date quoting.)

It seems like finite scheduling provides relatively little extra benefit over infinite scheduling given the very significant increase in complexity however accurate quoting at point of sale is practically a business imperative now.

Inputs

Which we have:

  • Material procurement constraints (e.g. maximum lead time of unavailable material for an order.)
  • Rough order priorities (weighted priority based on need date.)

Which we don’t have and would improve the schedule:

  • Precedence of shop orders relative to one another (e.g. parent assembly order to sub assembly orders.) Replaces order priorities with exact sequence/dependency information.

    This could be derived from MRP but the lack of links between supplies and their consuming demands in IFS necessitates producing such data ourselves.

  • Potential operation overlap details.

  • Distinct setup and run times.

Which would be required for scheduling labour:

  • Labour classes and employee assignments sufficient to provide the “pools” of workers suitable for each operation.

    An alternative that could be used would be to group employees by work center based upon the work centers they’ve booked against recently (e.g. the last six months.)

  • Actual labour run times for operations, distinct from the machine run time.

  • Crew size requirements (e.g. for assembly ops requiring more than one person)

In reality there is nothing preventing us from scheduling against labour constraints at present. The above would all make the input data more accurate and therefore improve the quality of the schedule but none of them are required (except the grouping of employees and identification of group(s) suitable for operations but the work center based grouping would be sufficient to start with.)

Scheduling labour would also require a change to how we view work center resource availabilities. At present the work center availabilities are based on a rough approximation of the labour availability for that work center. A schedule derived from the constraints of actual labour availability and the labour derived work center availabilities would be quite severely hindered in it’s utility.

Therefore when labour is used as a scheduling constraint the work center constraints should be relaxed to better reflect their nature as machines/tools for the jobs. The only real constraints they impose is the number of distinct resources that are available (i.e. the number of concurrent jobs they can run) and periods of unavailability due to maintenance.

Glossary

  • “makespan”—the total duration of the proposed solution, from the start of the first job until the end of the last.
  • “flow shop”—a scheduling environment of n × m jobs where the processing sequence is the same for all jobs.
  • “job shop”—a scheduling environment of n × m jobs where the processing sequence may be different for different jobs.

References

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment