Insights

Best route scheduling is an intractable problem, in both the intangible world of mathematics and the tangible world of job shop manufacturing. The contention between multiple jobs and limited resources quickly overwhelms even the most powerful computers’ ability to solve the problem. This paper looks at the origins of the problem and suggests approaches to decrease overall production time for a group of jobs.

What is the Job Shop Scheduling Problem?

The real question being asked here is: what is the best way to do the work that needs to be done in order to produce a specified group of jobs in the shortest amount of time. The more formal definition reads more like: Given n jobs j1, j2,…jn , each unique in the path they must or could follow through the shop, but sharing resources within the shop, and minimizing the production time for the job list as a whole, what is the best ordering of jobs and steps within jobs.

CPM v GPM in the Job Shop

Graphical Path Method (GPM), an alternative to CPM, allows a graphical model of the planned production schedule. Non-polynomial evaluation aided by real-time graphical feedback through the logic diagramming method (LDM). GPM uses planned dates selected by the planner, which can reside anywhere on or between CPM’s early and late dates. Planned dates are not calculated. Floats are calculated by working through the network path and adding the activity level floats and gaps between activities. This is not intuitive to experienced CPM schedulers because CPM would calculate early dates. The critical difference between CPM and GPM is the availability of back float, or “drift” as GPM describes it. Drift is the number of days an activity can move to earlier dates without forcing an earlier start day for the project. Drift is a calculated activity attribute that measures the number of days an activity may backslide or extend to an earlier position without forcing an earlier project start or earlier interim release date.