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.