Optimizing Production Planning and Scheduling using EFA Algorithm

Makespan - Production Planning & Scheduling Solutions Ltd.

EFA, a better way to Optimize Production
in Job Shops and Flow Shops

In factories producing a variety of items, mainly job shops, flow shop and assembly lines, optimal scheduling, which essentially depends on job sequencing and lot sizing, is highly problematic. The problem is known as “NP HARD” and no mathematical theory is able to handle it. A significant advance in understanding the problem and the way to solve it was achieved by two well known approaches, the Bottleneck Approach (later TOC) and JIT. However the applications of these approaches in the dynamic environment of job shops and flow shops show that still there is a long way to go to reach the optimal solution. Many scheduling software systems still use simple rules of thumb like SPT, FCFS, EDD, FIFO etc while sophisticated production planners rely on their Common Sense to optimize the flow process. This article introduces the Evenly Feeding Algorithm (EFA) and compares it to the Bottleneck Approach and JIT, using a simple example as a case study.

A Simple Case Study

Table-1
Product/Job	QTY	M-1	M-2	M-3
Prod’-A	100	1.8	0.5	0.5
Prod’-B	100	0.5	2.5	0.5
Prod’-C	100	0.7	0.5	1.5
Total Work Load		300	350	250

In order to explain the EFA and illustrate its advantage over the Bottleneck Approach and JIT we use a simple example as a case study: Three Products/Jobs A, B and C that have the same due date and priority are manufactured in three serial work centers (M) in the order M-1→ M-2 → M-3. The quantity and process time per item (in minutes) are given in TABLE-1 (set-up times=0). Assume that process batch equals to 100 units, and the minimal transfer batch from one work center to the next one equals to 1 unit. The objective is to manufacture the products in the shortest total lead time. As can be seen in the bottom line of Table 1, the maximum workload is 350 minutes (at M-2). This is also the minimum theoretical total lead time. M-2 has the accepted name “the Bottleneck”, but looking at details shows that M-2 is not the only bottleneck.

Fig-1 shows the workload distribution caused by jobs A, B and C separately, each job locating the bottleneck [BN] in another work centre. If for example job A is processed first, M-1 will be a bottleneck. The bottleneck location might move to another work center when the next job is processed and so forth. Remark: in job C work center M-2 starts working right from the beginning instead of waiting for 20 minutes. This enables work center M-3 with the maximum workload -150 minutes, to start working from the beginning (actually right after work center M-2 had finished the processing of the 1st item).
The Gantt charts for three options (out of six) which are presented in Fig-2 show that the total lead time is 370 minutes in sequence C-B-A, 450 minutes in sequence B-A-C and 580 minutes in sequence A-B-C. The total lead time of sequence A-B-C is longer by 56% than the total lead time of sequence C-B-A. (the other sequences are C-A-B -500 minutes, A-C-B -500 minutes and B-C-A -450 minutes).

Fig-2 shows clearly four facts:
1) The bottleneck location is not fixed; there are two or three temporary bottlenecks during the production cycle. The “moving” bottleneck from M-1 to M-2 and M-3 is seen clearly in sequence A-B-C. Remark: A work center is a bottleneck at a given time if any change in its process time affects the total lead time respectively.
2) A temporary bottleneck can be M-2 with the highest workload as well as M-1 and M-3 with the lowest workload.
3) A work center might become a temporary bottleneck after it had been idle for a long time (e.g. M-3 in sequences A-B-C and B-A-C).
4) There is a strong correlation between the total lead time and the number and duration of the temporary bottlenecks.

The EFA Solution
Our first steps in developing the EFA rested on Common Sense. By way of example, let us look at the temporary workload of the three work centers as caused by the first job: A, B and C shown in Fig-1. If job A starts first, the high temporary workload of M-1 forces M-2 and M-3 to remain idle at the beginning, or to work at partial capacity. At the same time jobs B and C are waiting to be processed. The best solution is to start with job C. The high temporary workload is at M-3; since M-3 is the last work center in the process it can’t “starve”

the other work centers and slow the material flow. By choosing job B next, the high temporary

workload will move to M-2. It will partially starve M-3, but this is a better choice than job A

which will place the bottleneck at M-1 and starves both M-2 and M-3.
Hence the sequence received by EFA is C-B-A.

The sequencing task becomes more difficult as the systems become more complicated and production doesn’t start from an empty floor. One of the irritating things that can be seen during production is a temporary bottleneck at a work center that only a short time before had been idle or working at partial capacity. Production managers try to avoid this development by looking for the idle machines during production. When they find one, which is scheduled for heavy loading a little later, they quickly feed it by changing the sequence, splitting batches etc. What they are actually trying to do is reduce unnecessary temporary bottlenecks.

As we turned over in our minds these scenarios, we soon came to realize that Common Sense alone wasn't enough. In order to improve the planning results it is necessary to identify the temporary bottlenecks work centers and feed them before they run out of material. This led to the development of the Evenly Feeding Algorithm.
EFA regards the temporary bottlenecks as the main obstacles to smooth and maximum material flow. A temporary bottleneck can be any work center, even one whose workload is the lowest. Temporary bottlenecks usually prolong the total lead time and sometimes cause other work centers which are fed by them to work at partial capacity and become temporary bottlenecks later on.
Actually, each job engages the work centers differently; it depends on its unique parameters such as process times, setup times, common setups etc. Hence the number of temporary bottlenecks, their location, and duration depends much on the jobs sequence and lots size. In order to achieve maximum material flow, temporary bottlenecks must be avoided. If they do appear, their location must be controlled in order to minimize their negative impact upon the production process. This is done by splitting batches into reasonable minimal and practical quantities and sequencing them in a way, which feeds most of the work centers without “starving” them beyond a given amount of time (slack time). By continually tracking various parameters such as idle time, workload etc. in every work center, EFA selects the job that will feed the machines evenly, thus preventing the formation of unwanted and unnecessary bottlenecks.

The Bottleneck Approach [BA] Solution
The Bottleneck Approach (TOC) regards a bottleneck as the resource with the highest average utilization rate during the planning period. The bottleneck location is determined once and it remains constant during the whole planning cycle. In order to optimize production, the bottleneck resource should work continuously. The system tries to ensure continuous work of the bottleneck by creating a buffer of safety stock in front of it.
OPT-Optimize Production Technology, the first and original bottleneck software, separates the scheduling of the bottleneck from the other resources. At first the bottleneck resource and all operations following the bottleneck are scheduled “forward”. The planning of the non-bottleneck resources which by definition have excess capacity is less important and is derived “backward” from the bottleneck schedule.

Let's try to solve our example using the [BA] principles. As can be seen in Table 1, M-2 is the bottleneck. The first job to start with is B, which ensures quick loading and continuous work while creating a buffer in front of the bottleneck (because the process rate of M-1, the feeding work center, is higher than M-2). The second job could be A or C (in both the bottleneck works continuously and the total lead time is the same). The Gantt chart of the [BA] sequence B-A-C can be seen in Fig-2.
If we compare the results of [BA] with those of EFA, we can see that the total lead time achieved by EFA is shorter by 17%. The reason is seen clearly in the [BA] Gantt chart, at time point 200 minutes. At this point, M-3, which had been idle, starts working. It becomes later a temporary bottleneck and prolongs the total lead time up to 450 minutes. (Note that in the optimal EFA solution, the bottleneck does not work continuously).

Table-2
Product/Job	QTY	M-1	M-2	M-3
Prod’-A	100	1.5	0.5	0.5
Prod’-B	100	0.5	1.5	0.5
Prod’-C	100	0.5	0.5	1.5
Total Work Load		250	250	250

An interesting case arises by changing the process parameters to those presented in Table-2. The total load of the three work centers is the same -250 minutes. From the [BA] point of view, all the work centers are bottlenecks, and none of the sequences have any priority. In such cases, the [BA] can inadvertently generate the worst schedule possible! On the other hand, from the EFA point of view, since each job creates a temporary bottleneck in another work center, the jobs are sequenced in the same way as in the case study, i.e. according to the optimal order C-B-A. Note the substantial difference between the total lead time of the optimal and the longest sequence, 250 minutes (C-B-A) and 450 minutes. (A-B-C) respectively. This is not the only case in which the [BA] is unable to give priority to any sequence. When the bottleneck is the first work center in the process, no matter what sequence is selected, it will always work continuously.
A particular case is a bottleneck work center whose utilization rate over a long period is significantly higher than that of the other work centers. In this case, no matter what the planning method is, sooner or later the bottleneck will work continuously and a large amount of stock will pile up in front of it. The production rate of the whole line will be reduced to the bottleneck rate. In such an instance, we end up by diverting overtime, more shifts etc. to support the bottleneck resource. At this point, the process ceases to be a dominant bottleneck from the planning point of view.

The JIT Solution
JIT is known especially in its unique PULL and KANBAN control system; this article deals only with its scheduling and sequencing way. JIT schedules jobs by splitting the process batches into many small ones, making a product mix, and freezing it for the planning period. For example, if we have to produce 200 units of product A, 500 units of product B, and 700 units of product C, we can create a mix of 2 A's, 5 B's and 7 C's and produce it over and over for 100 times. This enables us to significantly reduce the total lead time and WIP.
Looking at our example in Fig-2, sequence B-A-C (or any other sequence): if we split the process batches into two, each batch consisting of 50 units, and process them in the sequence B1-A1-C1-B2-A2-C2, the total lead time will be 400 minutes instead of 450 minutes in B-A-C sequence. In addition, the WIP inventory will be reduced. Splitting the process batches into smaller quantities will reduce the total lead time and the result would be about the same as obtained by the EFA (without splitting).

The logic behind this procedure is very close to the EFA in that each product mix loads all the work centers proportionally to their total load. In other words, this is another, more simple way to feed all the work centers evenly. However, the simplicity is somewhat deceptive. Implementing JIT in the dynamic flow or job shop environment is not always possible since it is difficult to define product mix and to freeze it for a reasonable period, as required by JIT. Furthermore, implementing JIT is sometimes very inefficient. When setups exists, JIT's ability to reduce the total lead time decreases, indeed it could actually prolong the total lead time. The addition time is influenced by the multiplication of the setup times by the number of small batches. In addition, numerous process batches usually means increased handling of raw materials, quality control activity, route cards, etc. On the other hand, the known benefit of JIT, inventory reduction, is effective only when raw materials are supplied as needed and when each small batch of finished goods is sent immediately to the customer. If these events do not occur, the total amount of raw materials finished goods and WIP inventory will remain unchanged or even grow.

Summary
The EFA is an optimization algorithm, its objective being to increase the firm's profits. This is achieved by better utilization of the plant's resources, namely reducing the total lead time and increasing the throughput. Such actions obviously and substantially enhance profitability. Shortening lead times decreases manufacturing and WIP expenses. In addition it makes it possible to accept and produce more customer orders in a given period. The extra throughput, with almost no additional cost (except raw materials) and the reduction of WIP expenses affects the profit considerably.