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 AS_{1}, AS_{2}, BS_{2} and BS_{3} which does not require calculation of the idle time. However, the other two approaches i.e., either taking the sum of AS_{1}, BS_{1}, BS_{2}, BS_{3} or the sum of AS_{1}, AS_{2}, AS_{3}, BS_{3}, 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., S_{1},
S_{2} and S_{3}, 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 nonlinear 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 interstage 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 3product (A, B, C) batch production
process with each, requiring three processing stages (S_{1}, S_{2},
S_{3}). 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., V_{AB1}
located in between AS_{1} and BS_{1}, V_{AB2} located
in between AS_{2} and BS_{2}, V_{AB3} located in between
AS_{3} and BS_{3}, V_{BC1} located in between BS_{1}
and CS_{1}, V_{BC2} located in between BS_{2} and CS_{2}
and V_{BC3} located in between BS_{3} and CS_{3}.
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., BS_{1} and AS_{2}
and BS_{2} and AS_{3}. For each comparison made, note on the
element that has the larger value. Suppose the comparison outcome shows BS_{1}
has a larger value than AS_{2} and BS_{2} has a larger value
than AS_{3} as indicated by the direction of the two arrows in the matrix
below.
Secondly, another comparison is made between the sum of BS_{1} and BS_{2} and the sum of AS_{2} and AS_{3}. 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 

M_{i,j} is used to represent the duration of the process in stage
j for product i and V_{i,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 V_{AB1}, V_{AB2} and V_{AB3} are;
where, V_{AB1} = V_{0,0}, V_{AB2} = V_{0,1}, V_{AB3} = V_{0,2}, AS_{2} = M_{0,1}, AS_{3} = M_{0,2}, BS_{1} = M_{1,0}, BS_{2} = M_{1,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, V_{BC1},
V_{BC2} and V_{BC3}. Suppose BS_{2} has a larger value
than CS_{1} and CS_{2} has a larger value than BS_{3}
as indicated by the direction of the two arrows in the matrix below.
Now, suppose the next comparison outcome between the sum of CS_{1}
and CS_{2} and the sum of BS_{2} and BS_{3} shows that
the earlier sum is greater than the later, the formulae used now for calculating
V_{BC1}, V_{BC2 }and V_{BC3 }as shown in Table 9 are:
where, V_{BC1} = V_{1,0}, V_{BC2} = V_{1,1}, V_{BC3} = V_{1,2}, BS_{2} = M_{1,1}, BS_{3} = M_{1,2}, CS_{1} = M_{2,0}, CS_{2} = M_{2,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 = AS_{1}+AS_{2}+AS_{3}+V_{AB3}+BS_{3}+V_{BC3}+CS_{3} 
• 
Makespan = AS_{1}+V_{AB1}+BS_{1}+V_{BC1}+CS_{1}+CS_{2}+CS_{3} 
• 
Makespan = AS_{1}+AS_{2}+V_{AB2}+BS_{2}+V_{BC2}+CS_{2}+CS_{3} 
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., (M_{i,0} + M_{i,1}) and (M_{i1,1} + M_{i1,2}) where (i = 1,2,…n1), 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:
Where:
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 interstage
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 interstage 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.