Job shop scheduling is a pivotal process for manufacturers, consuming 10% of staff time for pharmaceutical manufacturers, as reported by McKinsey. On the other hand, finding a non-academic resource on this complex mathematical problem is difficult and lack of understanding on the issue might negatively impact some manufacturers’ profitability.
Addressing the challenge of finding reader-friendly guides on job shop scheduling problems, this article serves as a simplified guide for manufacturing executives, the objective of which is to provide a clear understanding of the scheduling problem along with potential remedies. The content is structured to first explore the definition and offer a simplified example of the job shop scheduling problem. Subsequently, it introduces the role of AI in optimizing scheduling problems for various objectives. Finally, a case study is presented, underscoring the significance of leveraging AI-driven advanced planning systems to maximize profits.
What is the Job Shop Scheduling Problem?
The Job Shop Scheduling Problem (JSSP) is an NP-hard problem, aiming to find near-optimal ways of allocating jobs or work orders to machines and lines. The primary objectives include minimizing costs, delays, inventory, and other relevant factors. Within the realm of work order management, JSSP stands out as a critical step.
Boston Consulting Group emphasizes its significance, stating that the disparity between effective and average job shop scheduling can result in a variance of up to 30 minutes of additional productive time per day for a manufacturer.
Numerous factors contribute to the complexity of JSSP within a shop floor, including:
- Number of work orders
- Limited number of machines
- Inability of machines to process different work orders simultaneously
- Interdependence of work orders (e.g., packaging contingent on granulation)
- Cost considerations
- Different due dates
- Priority levels of customers
- Products’ shelf life
- Legal agreements (incurring potential OTIF penalties), and more.
Job Shop Scheduling Problem Example
To illustrate the Job Shop Scheduling Problem, let us consider a simplified example aiming to minimize delays in production involving only four work orders or jobs. For the sake of simplicity, we will assume there is no interdependency between work orders, implying that it is possible to continue production without the need to prioritize among them.
Let us schedule Work Order 1 (WO 1), Work Order 2 (WO 2), Work Order 3 (WO 3), and Work Order 4 (WO 4), with the following information:
As there are a total of 4 work orders, there are 4! or 24 different ways to sequence these work orders. However, thanks to the Branch and Bound methodology, there is no need to explore all possible sequences. By constructing decision trees and employing backward induction, we can first identify which work order should be initiated last to minimize delays. Subsequently, we can proceed to determine the work order that needs to be started first.
Determining Last Work Order (Step 1)
To decide which work order to schedule last, we calculate the total duration required to complete all work orders, which is 24 days (summing up the duration days from the table above). The implications of scheduling each work order last are as follows:
- Allocating WO 1 as the final job results in at least 18 days of delayed delivery.
- Allocating WO 2 as the final job results in at least 19 days of delayed delivery.
- Allocating WO 3 as the final job results in at least 10 days of delayed delivery.
- Allocating WO 4 as the final job results in at least 8 days of delayed delivery (see image below).
As the scenario where work order 4 is scheduled as the last job results in the minimum of delay among the 4 scenarios, the algorithm should branch from this specific scenario.
Determining Third Work Order (Step 2)
Now, let us proceed with scheduling the third work order. Since we already have a confirmed 8 days of delay, and the completion duration for work order 4 was 9 days, the completion duration for remaining 3 work orders available is 15 days. Here are the implications of scheduling each work order as the third job:
- Allocating WO 1 as the third job results in an additional 9 days of delayed delivery on top of the initial 8 (9+8=17 total delay).
- Allocating WO 2 as the third job results in an additional 10 days of delayed delivery on top of the initial 8 (10+8=18 total delay).
- Allocating WO 3 as the third job results in an additional 1 day of delayed delivery on top of the initial 8 (1+8=9 total delay).
As the scenario where work order 3 is scheduled as the third job results in the minimum of delay among the 3 scenarios, the algorithm should branch from this specific scenario.
Determining Second & First Work Orders (Step 3)
Now it is time to find which work order must be scheduled as the second job to minimize delay. Now the completion duration for the remaining 2 work orders available is 8 days. We have already 9 days of delay. Here are the implications of scheduling each work order as the second job (see image below):
- Allocating WO 1 as the second job results in an additional 2 days of delayed delivery on top of the initial 2 (9+2=11 total delay).
- Allocating WO 2 as the second job results in an additional 3 days of delayed delivery on top of the initial 3 (9+3=12 total delay).
As the scenario where work order 1 is scheduled as the last job results in the minimum of delay among the 2 scenarios, the algorithm should branch from this specific scenario. Take note that, in this case, the remaining work order 2 must be scheduled as the first task with no additional delays. With a total delay of 12 days, the ideal sequencing then becomes WO 2, WO 1, WO 3, and WO 4.
It is crucial to highlight that this example is oversimplified—not because there were only four work orders, nor because the figures we calculated prevented us from looking at other potential decision tree branches, but rather because it only takes delay reduction into account. The expense, legal restrictions, and customer importance that scheduler teams should consider are not mentioned.
For instance, it would be inefficient to schedule work order 4 as the last job if its late delivery results in OTIF fines. Manufacturers need to increase their agility in order to respond quickly to various conditions. As we shall cover below, AI can be a useful tool for manufacturers in this regard.
Job Shop Scheduling in AI
AI streamlines schedulers’ decision-making process. According to Boston Consulting Group, implementing AI cuts the scheduling team’s work hours by around 50%. The reason for this is that AI models can quickly find almost ideal solutions when they are equipped with specific algorithms, heuristics, and computing production capacity.
Additionally, because AI scheduling systems may be trained to tackle various optimization problems, factories can become more agile. Our scheduling algorithms, for example, optimize for just-in-time manufacturing, OTIF maximization, cost minimization and more.
Job Shop Scheduling Case Study with AI
Last year, we engaged in discussions about AI schedulers with one of our clients specializing in the production of chemical cleaning materials. Although they were utilizing other tools within the Digital Factory Platform, they were manually sequencing tasks and not using our Scheduler. When we presented the potential financial gains they might be missing out on by not optimizing their scheduling, their initial response was, “Our scheduling is already optimal.”
To challenge this belief, we initiated a pilot implementation of our AI scheduler, focusing on scheduling jobs for six production lines. We then conducted a comparative analysis between the cost of AI-driven scheduling and their manual scheduling, considering their cost function, which amounted to $25 per hour for operators. Additionally, we factored in that operators are paid until the end of their shift once they start.
The pilot case demonstrated that for just six production lines, AI-driven job shop scheduling not only reduced costs by $100,000 per month but also resulted in a substantial 20% reduction in cycle time. This stark revelation highlighted the significant potential for improvement that AI-driven job shop scheduling could bring to their operations if it is implemented for all lines.
Improve Your Scheduling with SCW.AI
SCW.AI’s cloud Scheduler module, integrated into the Digital Factory Platform, is designed to enhance the agility of manufacturers through:
- AI Algorithms: These algorithms automate job shop scheduling with different objectives, as demonstrated in the accompanying video.
- Schedule Adherence Report: This report offers insights into key performance indicators (KPIs) such as schedule adherence, schedule compliance, and schedule attainment. These metrics measure the effectiveness of scheduling activities.
- Maintenance Performance Report: This report aids manufacturers in transforming their maintenance approach from reactive to preventive or even predictive. It includes metrics such as mean time to failure, mean time to repair, and mean time between failures.
- OTIF Report: This report provides granular-level OTIF scores, aiding manufacturers in prioritizing deliveries to specific customers.
If you want to learn more information regarding job shop scheduling and different optimization objectives contact us.
To explore how our Scheduler can contribute to making your manufacturing process more agile, you can schedule a demo now!
