Abstract: The present research proposes a novel approach based on matrix to determine the makespan of a batch process adopting zero wait transfer policy. The proposed approach uses simple mathematical formulae, applied on a matrix representing the batch process recipes according to a selected production sequence. Rearrangement of the matrix rows according to the varied production sequences possible for the specified batch process recipes enables the makespan to be determined for each sequence. Designer is then provided with the production sequence options with its corresponding makespan from which a selection could be made according to the process conditions.
INTRODUCTION
It is usually practiced in chemical industry especially which is dealing with processing of paint, food, pharmaceuticals and specialty chemicals, that batch process is normally preferred over the continuous process due to ease of operation and flexibility to meet frequent changes in product specifications according to current market demand. Significant improvement in production systems has made it possible to; (i) produce wide range of products specifications (multiproduct process) and (ii) produce simultaneously different products (multipurpose process), by making use of the same facility and resources (Orçun et al., 2001; Balasubramanian and Grossmann, 2002). In each of the above case, scheduling appears to be one of the most important design considerations that require significant attention. One of the important aspects in scheduling batch process is the selection of inter stage transfer policy to transfer intermediates from one stage to another. Sometimes, the intermediate product produced in a batch process is not stable and must be transferred immediately to the next stage. This type of batch process observes zero wait transfer policy (Birewar and Grossmann, 1989; Jung et al., 1994; Ryu and Pistikopoulos, 2007).
Despite comprehensive research to solve the batch scheduling problem, there are still opportunities exist for new work to improve its design method. Determination of batch production sequence that produces minimum makespan based on specified batch process recipes is recognized as one of the most important design parameters as it helps to decide for the best scheduling design. Just by considering makespan as an independent decision parameter would permit designer to select the best sequence from the various possible batch production sequences. The literature revealed mostly the use of mathematical approaches such as MILP and MINLP in the formulations for determining minimum makespan and the corresponding optimal batch production sequence (Voudouris and Grossmann, 1992; Kim et al., 1996; Caraffa et al., 2001; Burkard et al., 2002). Though it is capable of providing the optimal solution but also offers mathematical complexity in formulating the batch scheduling problem. The use of traditional Gantt chart method is simple and could also generate design options that are near optimal based on makespan calculation. However, the procedures are very tedious and difficult to implement on computer programming, hence not attractive.
In this study, a new matrix approach is proposed to quickly calculate the makespan for all possible batch production sequences derived from specified batch process recipes. The batch process recipes are firstly arranged in a matrix according to a selected sequence. A series of simple procedure using simple mathematical formulae wherever applicable, is then applied to the matrix to calculate the makespan. By rearranging the row of the matrix to reflect changes in the production sequence, the makespan for other possible sequences could be calculated. In addition, the approach also determines possible idle time existence in the production sequence which could offer improvement opportunity. Overall, the approach produces the result on makespan calculation for all possible production sequences from which selection could be made by designer according to the process conditions.
MAKESPAN DETERMINATION USING GANTT CHART METHOD
Calculation of makespan requires data particularly on the number of products to be produced and its corresponding batch process recipes containing the number of process stages and the processing time for each stage. Based on a selected production sequence, the data could be used to draw a Gantt chart before the makespan could be determined. The procedure is repeated for other possible production sequences to determine their corresponding makespan. In addition, the presence of idle time in each sequence could also be determined.
Example 1 and 2 demonstrated below is based on a batch process where each product follows the same sequence of operations on all process stages. The batch process consist of three main unit operations (stages) i.e., mixing, reaction and separation stage. The cleanup and transfer times are assumed to be negligible (Biegler et al., 1997).
Example 1. (Makespan of two products): Table 1 shows the batch process recipes arranged accordingly for a production sequence producing two products namely A followed by B. From the Gantt chart as shown in Fig. 1, it is observed that there are two locations where idle time are readily available within the process i.e., at the end of stage 1 and stage 3 (shaded area), while there are none for stage 2. Table 2 shows the summary of the idle time results.
Careful examination on the Gantt chart reveals calculation of makespan using three different approaches. One approach is to take the sum AS1, AS2, BS2 and BS3 which does not require calculation of the idle time. However, the other two approaches i.e., either taking the sum of AS1, BS1, BS2, BS3 or the sum of AS1, AS2, AS3, BS3, need to account for the idle time calculation prior to determining the makespan. As expected, the makespan calculated by all three approaches yielded the same answer i.e., 45 h.
For the purpose of verifying the observation, the batch process sequence is switched over as shown in Table 3. The inter stage idle times calculated using the Gantt chart method is shown in Table 4. The Gantt chart for the process producing product B first followed by product A is shown in Fig. 2. It could easily be observed that the process has idle time located at end of stage 1 and stage 3, while there are none for stage 2.
| Table 1: | Processing time of two products in three stages for production sequence AB |
| Table 2: | Idle time between three stages of two products from Table 1 |
| Table 3: | Processing time of two products in three stages for production sequence BA |
| Table 4: | Idle time between three stages of two products from Table 3 |
| Fig. 1: | Gantt chart for two products in three stages for production sequence AB |
| Fig. 2: | Gantt chart for two products in three stages for production sequence BA |
This shows the same situation from Fig. 1 although idle times between process stages are different. The calculation of the makespan is performed using the same three approaches and again it is found to produce the same answer i.e., 45.
Example 2. (Makespan of three products): In this example, the makespan calculation is performed for batch process producing three products namely A, B and C. The batch process recipes based on 3 stage operation i.e., S1, S2 and S3, are shown in Table 5.
From the constructed Gantt chart as shown in Fig. 3, the idle time is found to be located at the end of stage 1 and 3 for both products. The detail result is summarized in Table 6. The value of makespan is calculated from the Gantt chart as earlier done in example 1 above and the result is 50 h.
The procedure is again repeated for different batch sequence as shown in Table 7. The results for the presence of the idle time within the process as observed in the Gantt chart shown in Fig. 4 is summarized in Table 8. The calculated makespan is found to be 48 h.
From the observations made in the above examples, it can be concluded that the makespan and the idle time period and locations, varies with different batch process sequences. Although the procedure for determining both the makespan and the idle time using Gantt chart method appears to be relatively simple, it is expected to become extremely tedious as the problem size grows. This is in view of the number of repetitive construction of the Gantt chart needed to calculate makespan for all possible sequences of all products before coming up with the result of production sequence with minimum makespan.
THE PROPOSED MATRIX APPROACH
While the Gantt chart method looks relatively simple and capable of generating near optimal design options, it is actually tedious to conduct particularly for large number of products. On the other hand, most previous research conducted on batch scheduling design focused on the use of complex mathematical equations namely the mixed integer linear or non-linear programming. Although the approach is highly efficient in its execution, formulation of the batch scheduling design problem could be a problem to most designers as it requires considerable understanding in the use of high level mathematics.
The proposed matrix approach is a significant addition to our earlier study (Shafeeq et al., 2007) on the determination of makespan for zero wait batch processes. This work is more on developing some new algorithms for determining inter-stage idle times between every two stages of a zero wait batch process.
For the ease of understanding the matrix approach, details of the approach are described below using an example of a 3-product (A, B, C) batch production process with each, requiring three processing stages (S1, S2, S3). The duration of each stage is normally different for different product, subject to the batch process recipes. The transfer policy assumed is zero wait transfer i.e., intermediates can neither wait in the same stage nor there is any storage tank available to store intermediates.
| Table 5: | Processing time of three products in three stages for production sequence ABC |
| Table 6: | Idle time between three stages of three products from Table 5 |
| Table 7: | Processing time of three products in three stages for production sequence BAC |
| Table 8: | Idle time between three stages of three products from Table 7 |
| Fig. 3: | Gantt chart for three products in three stages for production sequence ABC |
| Fig. 4: | Gantt chart for three products in three stages for production sequence BAC |
The execution of the matrix approach follows the sequence described below.
Step 1: Arrange the batch process recipes in a matrix that represent the production sequence according to the arrangement below. In this case the scheduling is based on a production sequence where product A is produced first, followed by product B and lastly product C.
Step 2: Introduce slack variables in between the rows of the matrix. In the matrix shown, there are six slack variables introduced i.e., VAB1 located in between AS1 and BS1, VAB2 located in between AS2 and BS2, VAB3 located in between AS3 and BS3, VBC1 located in between BS1 and CS1, VBC2 located in between BS2 and CS2 and VBC3 located in between BS3 and CS3.
Step 3: Calculate the value of each slack variable by performing the following procedures to the elements of the two rows located above and below the slack variables. Firstly, comparisons are made on the value of the matrix elements between the two rows diagonally i.e., BS1 and AS2 and BS2 and AS3. For each comparison made, note on the element that has the larger value. Suppose the comparison outcome shows BS1 has a larger value than AS2 and BS2 has a larger value than AS3 as indicated by the direction of the two arrows in the matrix below.
Secondly, another comparison is made between the sum of BS1 and BS2 and the sum of AS2 and AS3. Now, suppose this comparison outcome shows the earlier sum is greater than the later one. For the two combined comparison outcomes above, a specific formula has been developed for determining the value of the slack variable and this is shown in Table 9.
For the purpose of generalizing the matrix approach, the standard matrix notation M is used to represent the batch process recipes according to a selected production sequence.
| Table 9: | Calculation of slack variable |
Mi,j is used to represent the duration of the process in stage j for product i and Vi,j is used to represent the corresponding slack variables introduced in between the rows of matrix M. The subscripts i and j stand for rows and columns respectively with initial value starting from zero.
For the matrix presented earlier, the developed formulae for calculating the slack variables VAB1, VAB2 and VAB3 are;
where, VAB1 = V0,0, VAB2 = V0,1, VAB3 = V0,2, AS2 = M0,1, AS3 = M0,2, BS1 = M1,0, BS2 = M1,1 for i = 1 in Table 9.
The same procedure is then repeated for the second and third row of the matrix element in order to calculate the next set of slack variables, VBC1, VBC2 and VBC3. Suppose BS2 has a larger value than CS1 and CS2 has a larger value than BS3 as indicated by the direction of the two arrows in the matrix below.
Now, suppose the next comparison outcome between the sum of CS1 and CS2 and the sum of BS2 and BS3 shows that the earlier sum is greater than the later, the formulae used now for calculating VBC1, VBC2 and VBC3 as shown in Table 9 are:
where, VBC1 = V1,0, VBC2 = V1,1, VBC3 = V1,2, BS2 = M1,1, BS3 = M1,2, CS1 = M2,0, CS2 = M2,1 for i = 2 in Table 9
Step 4: From the calculated values for the slack variables above, the makespan for the multi product batch process can be calculated using one of the following formulae;
| • | Makespan = AS1+AS2+AS3+VAB3+BS3+VBC3+CS3 |
| • | Makespan = AS1+VAB1+BS1+VBC1+CS1+CS2+CS3 |
| • | Makespan = AS1+AS2+VAB2+BS2+VBC2+CS2+CS3 |
Regardless of the formula selected, the calculated makespan produced the same answer.
GENERALIZED MATHEMATICAL EXPRESSION FOR N NUMBER OF PRODUCTS IN MATRIX APPROACH
On the basis of the observations made from the Gantt chart method, a set of generalized mathematical expressions were developed to determine the values of the slack variables and the makespan of the batch process with n number of products involving 3 process stages. The calculation procedures begin by making the required comparisons as stated in step 3 for the elements in the first and second row of the matrix before selecting the right formulae for determining the corresponding slack variables. This is then followed by adopting the same procedures for the elements in the second and third row of the matrix. The procedures are repeated until the elements in the last two rows have been addressed. Generally, the comparison outcomes as stipulated in step 3 for the matrix elements in each set of two rows addressed i.e., (Mi,0 + Mi,1) and (Mi-1,1 + Mi-1,2) where (i = 1,2,…n-1), could be categorized under three different conditions termed as Case A, Case B and Case C. For each case, three different set of formulae are available from which one is to be selected for the slack variables calculation. The guide for selecting the right formula is based on the condition as illustrated in Table 9.
Using the calculated value obtained for all the slack variables, the makespan is calculated using one of the following generalized mathematical expressions developed for n number of products with three batch process stages.
The application of the matrix approach on example 2 for which earlier Gantt chart method applied, is shown below to determine the makespan.
Comparisons are made on the matrix elements located in the first two rows and this resulted in the following conditions;
i.e., (8+12) is less than (20+5) and 20 is greater than 8 while 5 is lesser than 12.
This satisfies the condition under Case B1 (Table 9) and therefore, the slack variables values are calculated using the formulae;
The same procedures are then repeated for the elements in the second and third rows of the matrix. The comparisons resulted in the following conditions.
i.e., (5+6) is lesser than (12+3) and 12 is greater than 5 while 3 is lesser than 6.
The comparison outcome is referred to Table 9 and it is found that it satisfies Case B1. Therefore, the slack variables are calculated using the formulae;
Using the values of the slack variables and the required elements from the batch process recipes matrix, the makespan for the specified production sequence is calculated using one of the following formulae;
It is worth noting that the makespan value obtained above is for the production sequence where A is produced first, followed by B and lastly C.
Determination of optimum batch production sequence using matrix approach: The optimal batch process schedule is often based on designer’s choice for production sequence offering minimum makespan. A repetition on the whole procedures in the matrix approach above to address different production sequence will enable it to calculate the makespan for the corresponding sequence. Repeating it for all possible production sequences will lead to the makespan for each of the possible sequence to be determined. The possible number of production sequences could be determined using the simple permutation rule shown below:
P(n) = n! |
| P(n) | = | No. of possible batch production sequences |
| n | = | No. of products |
For example, the number of possible production sequences for three products namely A, B and C is P(3) = 3! = 6.
| Table 10: | Makespan and Interstage Idle times for all possible production sequences of three products A, B and C in three stages |
| Table 11: | Processing time of four products in three stages |
Based on the permutation result, the production sequences can then be derived, e.g., ABC, BAC, BCA etc., as shown in Table 10. For all the possible production sequences for the given batch process recipes as shown in example 2 (Table 5), the calculated makespan and inter-stage idle times using the matrix approach are shown in Table 10. The results obtained show the production sequence BAC produces the minimum makespan of 48 h. Apart from that, it is noticed that the inter-stage idle time varies with different production sequences.
To show the efficiency and robustness of the matrix approach, a much larger problem with four products is solved as illustrated in example 3 below for calculation of minimum makespan and interstage idle times. It is obvious that the number of permutations will become prohibitively large as shown in Table 12. The processing times data for four products A, B, C and D in three stages is given in Table 11.
Example 3:Table 12 shows the makespan calculation for every possible sequence of four products with respective idle times between process stages using matrix approach. The matrix approach is applied using a computer program developed for this purpose in Microsoft Visual C++ (Ver. 6.0)TM for faster execution.
| Table 12: | Makespan and Idle times for all possible sequences of four products A, B, C and D in three stages |
It is observed from Table 12 that production sequence DBAC offers minimum makespan of 65 h.
CONCLUSIONS
The study presented a new approach based on matrix for determining the makespan for a specified production sequence of a batch process using zero wait transfer policy. The approach is considerably easier to understand and does not require the knowledge of advanced mathematics. In addition, the procedures could be implemented easily on computer programming to speed up the makespan calculation, which is particularly required when determining the optimum production sequence from a given batch process recipes. Once the approach is programmed on computer, the user is only required to provide the batch process recipes and all the possible sequences with its corresponding makespan and inter stage idle time will be automatically determined. The approach is tested against the established mathematical programming approach and a similar optimum solution is obtained. In addition to determining the optimum solution, the approach could also produce other near optimal solutions from which designer could have flexibility to choose the one that meets optimum conditions. Such opportunity could lead towards the development of a more interactive design for batch process scheduling.