# Efficient Heuristic Solution Methodologies for Scheduling Batch Processor with Incompatible Job-Families, Non-identical Job-Sizes and Non-identical Job-Dimensions

M. Mathirajan, M. Ramasubramanian

► To cite this version:

M. Mathirajan, M. Ramasubramanian. Efficient Heuristic Solution Methodologies for Scheduling Batch Processor with Incompatible Job-Families, Non-identical Job-Sizes and Non-identical Job-Dimensions. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2019, Austin, TX, United States. pp.212-222, 10.1007/978-3-030-29996-5_25. hal-02460527

HAL Id: hal-02460527

https://inria.hal.science/hal-02460527

Submitted on 30 Jan 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Efficient Heuristic Solution Methodologies for Scheduling Batch Processor with Incompatible Job-Families, Non-Identical Job-Sizes and Non-Identical Job-Dimensions

M Mathirajan¹* and M Ramasubramanian²

¹Department of Management Studies
Indian Institute of Science
Bangalore 560012
Email: iiscmathi@gmail.com

²Loyola Institute of Business Administration
Chennai 600034
Email: rams.m@liba.edu

## Abstract

Efficient scheduling of heat-treatment furnace (HTF), a batch processor (BP, is very important to meet both throughput benefits as well as the committed due date to the customer, as the heat-treatment operations require very long processing time in the entire steel casting manufacturing process and accounts for large part of the total casting processing time required. In the recent time, there are good number of studies reported in the literature related to scheduling of BP associated with many discrete parts manufacturing. However, still there is very scant treatment has been given in scheduling of HTF problem, which has one of the unique job-characteristic: non-identical job-dimensions. This characteristic differentiates most of the other BP problems reported in the literature. Thus, this study considers a scheduling HTF, close to real-life problem characteristics, and proposes efficient heuristic solution mythologies.

**Keywords:** Heat-Treatment Furnace, Non-identical Job-Dimensions, Lower Bound, Greedy Heuristic Algorithm, Genetic Algorithm

## 1. Introduction

This study is motivated from steel-casting industries, particularly scheduling of heat-treatment furnaces (HTF), a batch processor (BP). Heat-treatment operation is one of the most important operations as it determines the final properties that enable components to perform under demanding service conditions such as large mechanical load, high temperature and anti-corrosive processing. The jobs (castings) in work-in-process (WIP) inventory, available in front of a HTF, vary widely in sizes and dimensions. Furthermore, jobs are primarily classified into several job families based on the alloy type. These job families are incompatible since the temperature requirement for low alloy and high alloy vary for similar type of heat-treatment operations required. These job families are further classified into various sub-families based on the type of heat treatment operations they required. These sub-families are also incompatible as each of these sub-families requires different combination of heat-treatment operations. The widely varying job sizes, job dimensions and multiple incompatible job family characteristics, which differentiate other batch processing operations across many other industries, create complexity in scheduling HTF.

It is also important to note that the heat-treatment operation requires lengthiest processing time (say between 6 h to 48 h) taking up a large part of total processing time. Because of these, the heat-treatment operation is a major bottleneck operation in the entire steel casting process. Considering the complexity and bottleneck nature of the heat treatment process the efficient scheduling of this operation to maximize throughput, in order to enhance productivity of the entire steel casting manufacturing process, is of importance to the firms. The concerns of the management in increasing the throughput of the bottleneck machine, thereby increasing productivity, motivated us to adopt the scheduling objective of minimizing makespan, as this objective can be a surrogate measure for maximizing throughput of the entire steel casting manufacturing process.

Accordingly, this study specifically focuses on developing a few simple Greedy Heuristic Algorithms and meta heuristic : Genetic Algorithm for the research problem of minimizing makespan (Cmax) on a batch processor (BP) with multiple incompatible job families (MIJF), where all jobs of the same family have

<footnote>* Corresponding Author</footnote>
identical processing times and jobs of different families cannot be processed together, non-identical job sizes (NIJS), non-identical job dimensions (NIJD), and non-agreeable release times and due dates (NARD).

The rest of this paper is organized as follows. Closely related literature review is presented in Section 2. In Section 3 several Greedy Heuristic Algorithms (GHA) and meta-heuristic algorithm: Genetic Algorithm (GA) are proposed to solve the problem. A lower bound procedure, which is considered as benchmark procedure, proposed for the research problem is discussed in Section 4. The computational experiment for evaluating the proposed heuristic algorithms is discussed in section 5. In Section 6 performance evaluation of the proposed heuristic algorithms is analysed and presented. Finally, conclusions and future research areas are discussed in section 7.

## 2. Related Literature Review

Scheduling BP in discrete parts manufacturing has been widely studied in the literature [10, 12-13], due to its intensive varied applications in the real-world industry. This research is motivated by heat-treatment operations, which is performed in heat-treatment furnace, in steel casting industries. One of the job's (casting's) characteristics on non-identical job dimension, which is not applicable in most of the applications of BP, is uniquely differentiate almost all the applications of BP listed in the literature. Furthermore, the non-identical job size and non-identical job dimension characteristics together are not addressed [1, 3-4, 11].

[14-15] considered the scheduling of an HTF with a single job-family. Subsequently, [16] extended their earlier studies, by considering the important additional real-life characteristics on multiple and incompatible job families and proposed a MILP model and demonstrated its computational intractability. Due to the computational intractability of scheduling of BP with incompatible job-families problems, recently, researchers have started to propose meta heuristic algorithms, in addition to simple greedy heuristic algorithms for scheduling of BP [5, 6, 17]. In the similar line, this study is proposing (a) a lower bound procedure and (b) a few greedy heuristics and meta heuristic: Genetic Algorithms for obtaining efficient HTF-schedule for the problem considered in this study.

## 3. Solution Methodologies

The development of nine variants of simple greedy heuristic algorithms (GHA) and meta heuristic: Genetic Algorithm (GA) to address the research problem considered in this study are discussed in this section. In the proposed GHA, first we sort the jobs by a criterion and then construct a set of batches (this process is called as Sort by Criteria and Construct Batch) by picking jobs from the sorted list. Finally, the set of batches constructed will be sequenced. Accordingly, the step-by-step procedure of the proposed GHA is as follows:

### 3.1 Greedy Heuristic Algorithm (GHA)

Step 1: Sort the list of jobs waiting in front of the BP using a specific sorting criterion.

Step 2(a): Select the first job family arbitrarily

Step 2(b): Select a set of feasible jobs from the selected job family, sequentially from the sorted list of jobs, and construct batch satisfying capacity restrictions on size, dimension and release time constraint:

Step 3: If the job list is not empty, select the next job family arbitrarily in the job list and repeat step 2 until the all the jobs in the job list are assigned to batches.

Step 4: Sequence the set of constructed batches using Earliest Batch Available Time (EBAT) rule, where, $EBAT = \text{maximum } \{\text{release time of all jobs in a batch}\}$

Step 5: Calculate the makespan using the following equation:

$$C_{max} = (\text{Number of batches resulted in the end of step 3}) \times (\text{processing time of a job})$$

The proposed GHA, presented here can be varied by introducing the nine different sorting criterions, as given in Table 1, and with that we have nine proposed variants of GHA for scheduling of HTF, considered in this study to minimize makespan:
## 3.2 Genetic Algorithm (GA)

GA has been applied to scheduling BP, related to semiconductor industry [2, 8, 18]. However, to the best of our knowledge, there are no studies considering GA for the problem configurations defined in this study. Accordingly, this study considers GA and use random key based representation for GA. Further, in order to fix value for GA-parameters (such as: number of generations, population size, crossover percentage, crossover probability, migration percentage and mutation percentage which are problem specific), we conduct a computational experiment. Based on the computational experiment conducted, the values of the GA-parameters are fixed as in Table 2.

Considering the value of each of the GA-parameters given in Table 2, the step-by-step procedure of the proposed GA for scheduling a BP with SJF, NIJS and NIJD is as follows:

Step 1. Generate a population of permutation sequences with size 25. This sequence is essentially job indices numbered from 1 to n.

Step 2. Sort the first sequence based on the job length using criterion SL mentioned in Table 1 with the maximum length job being first and the minimum length job being last.

Step 3. Repeat step 2 for the next eight sequences using criteria: SW, SH, SV, SS, SD, SVD, SSD, SR mentioned in Table 1.

Step 4. Generate random permutation sequences for the rest of the population.

Step 5. If the number of generations is less than or equal to 200, construct and schedule batches using the GHA mentioned in section 3.1 for each of the sequence. Else, go to step 16.

Step 6. Calculate the fitness value and the makespan of the schedule for each of the sequences.

Step 7. Sort the population of sequences based on the fitness value with lowest value on the top to highest on the bottom.

Step 8. Encode the permutation sequences using random keys.

Step 9. Keep top 20% of the population for migration to next generation.

Step 10. Select two chromosomes randomly from the population and apply crossover operation.

Step 11. Repeat step 10 to generate a total of 50% of population sequences which are the new set of off springs.

Step 12. Replace the middle 50% of the population with the new off springs.

Step 13. Generate rest 30% of the chromosome population randomly and replace the lowest 30% of the population.

Step 14. Sort each chromosome by random keys which are generated using crossover and mutation in descending order.

Step 15. Decode the chromosomes to get a new set of permutation sequences. Go to step 5.

Step 16. Output the best makespan value from the last generation.

Each of the proposed heuristic algorithms, presented here, is implemented in Turbo C++ language on a system with 1GB RAM, 2.4Ghz processor with Windows XP operating system.

# 4. Computational Experiments

The following proposed (a) benchmark procedure, (b) experimental design, and (c) performance measure are considered for empirical evaluation of the proposed heuristic algorithms:

## 4.1 Benchmark Procedure: Proposed Lower Bound (LB) Procedure

In BP literature, researchers have proposed LB procedures for evaluating the heuristic algorithms (Example: [7]). However, these studies do not consider NIJS and NIJD characteristics explicitly while
<table><caption>Table 1: Sorting Criterion considered for the proposed Variants of GHA</caption><thead><tr><td>Code</td><td>Sorting Criterion</td><td>Proposed Variants of GHA</td></tr></thead><tbody><tr><td>SL</td><td>Sort by Length and construct Batches</td><td>SLB</td></tr><tr><td>SW</td><td>Sort by Width and construct Batches</td><td>SWB</td></tr><tr><td>SH</td><td>Sort by Height and construct Batches</td><td>SHB</td></tr><tr><td>SV</td><td>Sort by Volume and construct Batches</td><td>SVB</td></tr><tr><td>SS</td><td>Sort by Size and construct Batches</td><td>SSB</td></tr><tr><td>SD</td><td>Sort by Due date and construct Batches</td><td>SDB</td></tr><tr><td>SVD</td><td>Sort by (Volume/Due date) and construct Batches</td><td>SVDB</td></tr><tr><td>SSD</td><td>Sort by (Size/Due date) and construct Batches</td><td>SSDB</td></tr><tr><td>SR</td><td>Sort by Release time and construct Batches</td><td>SRB</td></tr></tbody></table>

<table><caption>Table 2: GA-Parameter and its Value for GA-Implementation</caption><thead><tr><td>GA-parameter</td><td>Values of the parameter</td></tr></thead><tbody><tr><td>Number of generations</td><td>200</td></tr><tr><td>Population size</td><td>25</td></tr><tr><td>Migration percentage</td><td>20%</td></tr><tr><td>Crossover percentage</td><td>50%</td></tr><tr><td>Mutation percentage</td><td>30%</td></tr><tr><td>Crossover probability</td><td>0.6</td></tr></tbody></table>

developing LB procedure in scheduling a BP. Further, there are LB procedures proposed for three-dimensional bin packing problem [9] which consider only NIJD characteristic for obtaining LB. To the best of our knowledge, there are no studies which consider both NIJD and NIJS to obtain LB while scheduling a BP. This motivated us to develop an LB procedure for the research problem, considered in this study. Since our research problem is an extension of the three-dimensional bin packing problem, the LB procedure proposed by [9] is used with appropriate modification by considering both NIJD and NIJS characteristics to obtain LB on makespan. The proposed LB procedure in calculating LB on makespan for the research problem is as follows:

Step 1: Index the jobs in the non-decreasing order of the release times $r_j$

Step 2: Consider all the jobs to be available at time zero.

Step 3: Now calculate $C_{max}(f, j, n)$ for jobs $j, ..., n$ belonging to the first job family 'f' using the following sub-steps, taking appropriate processing time for the family

Step 3(a): Calculate LB on makespan by considering only NIJD called as $C_{max}^{NIJD}$ using the LB procedure proposed by Martello et al. (2000) with suitable modification.

Step 3(b): Calculate LB on makespan by considering only NIJS characteristic called as $C_{max}^{NIJS}$,

Step 3(c): Calculate LB on makespan by considering both NIJD and NIJS as

$$LBC_{max} = max\{ C_{max}^{NIJD}, C_{max}^{NIJS} \}$$

Step 4: Repeat step 3 for other job families in the list with their appropriate processing times

Step 5: Add all $C_{max}(f, j, n)$ and finally, add the release time of the job at head of the list with $C_{max}(f, j, n)$.

Step 6: Store the value $(r_j + C_{max}(f, j, n))$ in a separate list.

Step 7: Remove the job at the head of the list.

Step 8: Repeat steps 2-7 till the list is empty.
Step 9: Then LB for the research problem, LBC<sub>max</sub> is maximum of all the values store in the separate list. i.e. LBC<sub>max</sub> = max<sub>j=1,2,...,n</sub> {r<sub>j</sub> + Σ<sup>p</sup><sub>f=1</sub> Cmax(f, j, n)}; Where, p is number of job families

The procedure to obtain LB on makespan for scheduling a BP with SJF, NIJS and NIJD is implemented in Turbo C++ language on a system with 1GB RAM, 2.4Ghz processor with Windows XP operating system.

## 4.2 Experimental Design

Based on the problem configurations considered in this study, the parameters: Number of Jobs (n), Job size (s<sub>i</sub>), Job Dimension ((Length (l<sub>i</sub>), Width (w<sub>i</sub>) and Height (h<sub>i</sub>)), No. of Incompatible Job families (f<sub>i</sub>), Release time (r<sub>i</sub>) and Due date (di) are required data. Accordingly, an experimental design is developed (Table 3) to generate suitable test data. The range of intervals used in each uniform distribution is based on the observation from the user industries. The proposed experimental design for generating test problems is implemented in programming language C.

<table><caption>Table 3: A summary of experimental design for the research problem</caption><thead><tr><th colspan="2">Problem Parameters</th><th>No. of Levels</th><th>Values</th></tr></thead><tbody><tr><td colspan="2">No. of jobs (n)</td><td>6</td><td>25, 50, 75, 100, 125, 150</td></tr><tr><td rowspan="7">Job Parameters</td><td>No. of Incompatible Job families (f<sub>i</sub>)</td><td>2</td><td>4, 6</td></tr><tr><td>Release time (r<sub>i</sub>)</td><td>2</td><td>U[0,84], U[0,42]</td></tr><tr><td>Due date (di)</td><td>1</td><td>r<sub>i</sub> + U[168,240]</td></tr><tr><td>Job size (s<sub>i</sub>)</td><td>2</td><td>U[1, S/2], U[1, S/4]</td></tr><tr><td>Job length (w<sub>i</sub>)</td><td>2</td><td>U[1, W], U[1, W/2]</td></tr><tr><td>Job height (h<sub>i</sub>)</td><td>2</td><td>U[1, H], U[1, H/2]</td></tr><tr><td>Job length (l<sub>i</sub>)</td><td>2</td><td>U[1, L], U[1, L/2]</td></tr><tr><td colspan="2">Number of configurations</td><td colspan="2">6 x 2 x 2 x 1 x 2 x 2 x 2 x 2 = 384</td></tr><tr><td colspan="2">Number of instances per configuration</td><td colspan="2">10</td></tr><tr><td colspan="2">Total number of instances</td><td colspan="2">3840</td></tr></tbody></table>

In addition to the input provided for the problem parameters, mentioned in Table 3, we assume that there is only one BP which has BP-Size as S = 2500 kg; and BP-Dimension as L = 2500 mm, W = 1000 mm, and H = 1250 mm. Also, we assume the processing time of the job families as (a) 13, 15, 12, 10 respectively when number of job families are 4, and (b) 13, 15, 12, 10, 22, 18 respectively when number of families are 6.

## 4.3 Measures of Effectiveness

The performance of the proposed heuristic algorithms is compared using the performance measure: Average Relative Percentage Deviation (ARPD), indicating the average performance of proposed heuristic algorithms. The details of the calculation of the performance measures ARPD is as follows

Let C<sub>H</sub> be the makespan given by the proposed heuristic algorithm “H”. Let C<sub>LB</sub> be the Lower Bound on C<sub>max</sub> given by the proposed LB procedure. Then, the Relative Percentage Deviation (RPD) on instance ‘i’ for the proposed heuristic algorithm “H” is RPD<sub>H</sub>(i) and computed as follows:

$$RPD_{H}(i) = \left( \frac{C_{H}(i) - C_{LB}(i)}{C_{LB}(i)} \right) * 100 \quad (A)$$

The average RPD (i.e., ARPD) is calculated as follows:

$$ARPD_{H}(p) = \frac{\sum_{i=1}^{N} RPD_{H}(i)}{N} \quad (B)$$

Where, ARPD<sub>H</sub>(p) = ARPD of proposed heuristic algorithm ‘H’ for problem parameter p over N instances of planned configuration p
# 5. Performance Evaluation of the Proposed Heuristic Algorithms

To understand the performances of the proposed heuristic algorithms in comparison with the proposed LB, the randomly generated problem instances (3840 instances) is used. First, the proposed heuristic algorithms are run through each of the 3840 instances and the makespan values are recorded. Then, the LB-procedure is also run through each of these 3840 instances and the LB on makespan is obtained. With these values, for each problem instance the RPD value is computed using equation (A). Furthermore, Problem instance wise and the proposed heuristic algorithm wise, the $RPD_H(i)$ is used for calculating the scores: ARPD. The computed ARPD score is presented in Table 3.

From Table 3, we can observe that (a) the proposed GA outperforms the other proposed nine variants of GHA, and (b) within the proposed variants of the greedy heuristic algorithms: the variant of the GHA: *SWB* performs relatively better and the variant of the GHA: *SVDB* becomes relatively the second best one.

Finally, in order to check for the influence of individual problem parameters on the performance of the proposed heuristic algorithms in comparison with LB on makespan, the computed RPD score is used for statistical test. For this purpose, a statistical test: multi-factor (*heuristic algorithm*, *f*, *n*, *r*, *s*, *w*, *h*, *l*) ANOVA is used on the score: RPD. Since the normality and equal variance assumption failed for our data, we used *Mann-Whitney* non-parametric test for factors with two groups (*f*, *r*, *s*, *h*, *w*, *l*) and *Kruskal-Wallis* non-parametric test for factors with many groups (*heuristic algorithm*, *n*). The results of this analysis show that the there is an influence of all problem parameters, considered in this study, on the performance of the proposed heuristic algorithms.

# 6. Conclusion

This study addresses new problem configurations, close to real-life situations, while considering the scheduling of HTF. Due to the computational difficulty in obtaining optimal solution for the research problem defined in the study, nine variants of simple greedy heuristic algorithms and meta heuristic: Genetic Algorithm are proposed to obtain efficient scheduling. To understand the efficiency of the proposed heuristic algorithms, a LB-procedure is developed to obtain LB.

Based on the series of computational experiments conducted, considering 3640 randomly generated problem instances (representing 364 problem configurations), we observe that (a) the problem parameters considered in this study has influence on the performance of the heuristic algorithms, (b) the proposed LB-procedure is found to be efficient, and (c) the proposed GA outperforms among the proposed heuristic algorithms. However, the computational time required for GA increases as the problem size keeps increasing. Furthermore, in case the decision maker wants to choose a heuristic algorithm which is computationally advantageous among the proposed algorithms, the variants of greedy heuristic algorithm: *sort by width and construct batch (SWB)* is relatively better algorithm for the research problem considered.

There are several interesting future research directions. For example: (i) Appropriate modification and/or extension of LP-procedure and heuristic algorithms to address the situation on the availability of more than one non-identical BPs; (ii) It would be interesting to study with the objective of minimizing other completion time-based objectives such as total completion time, total flow time, etc.; and (iii) Considering due date-based objectives such as minimizing number of tardy jobs, maximum lateness, total tardiness, total weighted tardiness are possible future research directions for the research problem considered in this study.

# Reference

1. Baykasoglu A, and Ozsoydan (2018) Dynamic Scheduling of Parallel Heat Treatment Furnaces: A Case Study at a Manufacturing System. *Journal of Manufacturing Systems*, 46, 152-162

2. Cheragh SH, Vishwaram V and Krishnan KK (2003) Scheduling a Single Batch Processing Machine with Disagreeable Ready Times and Due Dates. *International Journal of Industrial Engineering-Theory Applications and Practice*, 10(2), 175-187.

3. Gokhale R, and Mathirajan M (2014) Minimizing Total Weighted Tardiness on Heterogeneous Batch Processors with Incompatible Job Families. *International Journal of Advanced Manufacturing Technology*, 70(9-12), 1563-1578.
<table><caption>Table 3: Performance of the proposed heuristic algorithm w.r.t. the score : ARPD based on LB</caption><thead><tr><th rowspan="2">Problem Configuration</th><th rowspan="2">No. of Instances</th><th colspan="9">Proposed variants of GHA</th><th rowspan="2">Proposed GA</th></tr><tr><th>SLB</th><th>SWB</th><th>SHB</th><th>SVB</th><th>SSB</th><th>SDB</th><th>SVDB</th><th>SSDB</th><th>SRB</th></tr></thead><tbody><tr><td>(n = 1, *, *, *, *, *)</td><td>640</td><td>18.9</td><td>17.5</td><td>18.4</td><td>17.5</td><td>19.5</td><td>22.9</td><td>17.8</td><td>20.6</td><td>26.3</td><td>4.4</td></tr><tr><td>(n = 2, *, *, *, *, *)</td><td>640</td><td>17</td><td>15.8</td><td>16.9</td><td>16.2</td><td>16.5</td><td>20.3</td><td>16.6</td><td>17.6</td><td>21.4</td><td>3.9</td></tr><tr><td>(n = 3, *, *, *, *, *)</td><td>640</td><td>24.9</td><td>20.8</td><td>22.3</td><td>21.1</td><td>28.4</td><td>29.3</td><td>21.5</td><td>29.2</td><td>29.5</td><td>9.2</td></tr><tr><td>(n = 4, *, *, *, *, *)</td><td>640</td><td>15.3</td><td>13.7</td><td>14.2</td><td>13.5</td><td>14.5</td><td>17.1</td><td>13.9</td><td>15.1</td><td>17.2</td><td>4.9</td></tr><tr><td>(n = 5, *, *, *, *, *)</td><td>640</td><td>12.9</td><td>11.4</td><td>12.6</td><td>11.6</td><td>12.4</td><td>14.2</td><td>11.8</td><td>12.6</td><td>14.6</td><td>4.3</td></tr><tr><td>(n = 6, *, *, *, *, *)</td><td>640</td><td>18.2</td><td>13.3</td><td>15.4</td><td>14.2</td><td>23.8</td><td>20.8</td><td>14.4</td><td>23.4</td><td>20.6</td><td>7.9</td></tr><tr><td>(*, f = 1, *, *, *, *)</td><td>1920</td><td>19.1</td><td>16.4</td><td>17.7</td><td>16.7</td><td>20.4</td><td>21.5</td><td>17</td><td>20.8</td><td>22.3</td><td>6.2</td></tr><tr><td>(*, f = 2, *, *, *, *)</td><td>1920</td><td>16.7</td><td>14.4</td><td>15.5</td><td>14.6</td><td>18</td><td>20</td><td>15</td><td>18.7</td><td>20.9</td><td>5.3</td></tr><tr><td>(*, r = 1, *, *, *)</td><td>1920</td><td>19.9</td><td>17.8</td><td>18.9</td><td>17.8</td><td>21.4</td><td>23.4</td><td>18.2</td><td>22.2</td><td>24.5</td><td>6.6</td></tr><tr><td>(*, r = 2, *, *, *)</td><td>1920</td><td>15.9</td><td>13.1</td><td>14.4</td><td>13.5</td><td>17</td><td>18.1</td><td>13.8</td><td>17.3</td><td>18.7</td><td>4.9</td></tr><tr><td>(*, *, s = 1, *, *)</td><td>1920</td><td>10.6</td><td>9.9</td><td>10.3</td><td>9.9</td><td>9</td><td>12.4</td><td>10</td><td>9.6</td><td>13.3</td><td>2.5</td></tr><tr><td>(*, *, s = 2, *, *)</td><td>1920</td><td>25.2</td><td>20.9</td><td>23</td><td>21.5</td><td>29.4</td><td>29.2</td><td>22</td><td>29.9</td><td>29.9</td><td>9</td></tr><tr><td>(*, *, *, h = 1, *)</td><td>1920</td><td>22.7</td><td>18</td><td>20.2</td><td>19</td><td>25.3</td><td>26</td><td>19.2</td><td>25.9</td><td>26.9</td><td>9</td></tr><tr><td>(*, *, *, h = 2, *)</td><td>1920</td><td>13</td><td>12.8</td><td>13</td><td>12.4</td><td>13.1</td><td>15.5</td><td>12.8</td><td>13.6</td><td>16.3</td><td>2.5</td></tr><tr><td>(*, *, *, *, w = 1, *)</td><td>1920</td><td>22.5</td><td>18</td><td>20.1</td><td>18.6</td><td>24.9</td><td>26.2</td><td>19</td><td>25.7</td><td>27</td><td>8.9</td></tr><tr><td>(*, *, *, *, w = 2, *)</td><td>1920</td><td>13.2</td><td>12.8</td><td>13.2</td><td>12.8</td><td>13.4</td><td>15.4</td><td>13</td><td>13.8</td><td>16.2</td><td>2.6</td></tr><tr><td>(*, *, *, *, l = 1)</td><td>1920</td><td>21</td><td>17.3</td><td>19.6</td><td>17.8</td><td>23.4</td><td>24.6</td><td>18</td><td>24</td><td>25.4</td><td>8.1</td></tr><tr><td>(*, *, *, *, l = 2)</td><td>1920</td><td>14.7</td><td>13.5</td><td>13.7</td><td>13.6</td><td>15</td><td>16.9</td><td>14</td><td>15.5</td><td>17.8</td><td>3.4</td></tr></tbody></table>
4. Huang J, and Liu JJ (2018) Hierarchical Production Planning and Real-Time Control for Parallel Batch Machines in a Flow Shop with Incompatible Jobs. Mathematical Problems in Engineering. [https://www.hindawi.com/journals/mpe/2018/7268578/abs/ accessed on 24/5/2019]

5. Hulett M, Damodaran P, and Amouie M (2017) Scheduling Non-identical Parallel Batch Processing Machines to Minimize Total Weighted Tardiness using Particle Swarm Optimization. *Computers & Industrial Engineering*, 113, 425-436.

6. Jia Z, Wang C, and Leung JY (2016) An ACO Algorithm for Makespan Minimization in Parallel Batch Machines with Non-identical Job Sizes and Incompatible Job Families. *Applied Soft Computing*, 38, 395-404.

7. Koh SG, Koo PH, Kim DC and Hur WS (2005) Scheduling a Single Batch Processing Machine with Arbitrary Job Sizes and Incompatible Job Families. *International Journal of Production Economics*, 98(1), 81-96.

8. Malve S, and Uzsoy R (2007) A Genetic Algorithm for Minimizing Maximum Lateness on Parallel Identical Batch Processing Machines with Dynamic Job Arrivals and Incompatible Job Families. *Computers and Operations Research*, 34(10), 3016-3028.

9. Martello S, Pisinger D, and Vigo D (2000) The Three-dimensional Bin Packing Problem. *Operations Research*, 48(2), 256-267.

10. Mathirajan M, Ravindra Gokhale, and Ramasubramaniam M (2014) Modeling of Scheduling Batch Processor in Discrete Parts Manufacturing. A Chapter in "Supply Chain Strategies, Issues and Models", Springer Verlag, UK, 153-192.

11. Mathirajan M, and Sivakumar AI (2006a) Minimizing Total Weighted Tardiness on Heterogeneous Batch Processing Machines with Incompatible Job Families. *International Journal of Advanced Manufacturing Technology*, 28(9), 1038-1047.

12. Mathirajan M, and Sivakumar AI (2006b) A Literature Review, Classification and Simple Meta-Analysis on Scheduling of Batch Processors in Semiconductor. *International Journal of Advanced Manufacturing Technology*, 29(9-10), 990-1001.

13. Monch L, Fowler JW, Mason SJ and Dauzere-Peres S (2011) A Survey of Problems, Solution Techniques, and Future Challenges in Scheduling Semiconductor Manufacturing Operations. *Journal of Scheduling*, 14(6), 583-599.

14. Ramasubramanian M, Mathirajan M, and Ramachandran V (2010) Minimizing Makespan on a Single Heat-Treatment Furnace in Steel Casting Industry. *International Journal of Services and Operations Management*, 7, 112-142.

15. Ramasubramanian M, and Mathirajan M (2011) Heuristic Algorithms for Scheduling Heat-Treatment Furnace of Steel-Casting Foundry Manufacturing. *International Journal of Advanced Operations Management*, 3, 271-289.

16. Ramasubramaniam M, and Mathirajan M (2013) A Mathematical Model for Scheduling a Batch Processing Machine with Multiple Incompatible Job Families, Non-identical Job dimensions, Non-identical Job sizes, Non-agreeable Release Times and Due Dates. 2013 International Conference on Manufacturing, Optimization, Industrial and Material Engineering (MOIME 2013).

17. Su L, Qi Y, and Jin L (2016) Integrated Batch Planning Optimization Based on Fuzzy Genetic and Constraint Satisfaction for Steel Production. *International Journal of Simulation Modelling*, 15(1), 133-143.

18. Wang CS, and Uzsoy R (2002) A Genetic Algorithm to Minimize Maximum Lateness on a Batch Processing Machine. *Computers and Operations Research*, 29(12), 1621-1640.