# Minimizing makespan in a batch-processing machine flow shop.

INTRODUCTION

A batch processing machine (BPM) is one in which can simultaneously process several jobs in a batch. They are commonly used in heat-treating ovens, semiconductor burn- in operations, chemical processes performed in tanks or kilns, testing process of electrical circuits, wafer fabrication process, pharmaceutical and construction materials industries, to name a few. The formal description to the flow shop with batch processing machines considered in this paper is as follows. There are N jobs available that each job j has processing time Pjm on batch-processing machine m. Each machine has a capacity equal to Cap and can process a batch only when the total size of all the jobs in a batch does not exceed its capacity. All the jobs have to be grouped into batches and these batches are processed in the same order, on all the machines. Thus the problem considered here is a permutation flow shop problem, i.e., all batches are processed on each in a fixed process flow.

The processing time of batch b (Bb) on machine m which is denoted by [P.sub.bm] is the longest processing times among all the jobs in that batch. Regarding this description, two important and distinct decisions, but dependent, made on BPM problems are: first, grouping jobs into batches, and second, scheduling the batches to improve a performance measure. A minimum makespan ([C.sub.max]) usually implies a high utilization of the machine(s). Therefore, reducing [C.sub.max] should also lead to a higher throughput rate. This concern led us to consider the makespan performance measure as the scheduling objective. In theory of scheduling, [C.sub.max] is equivalent to the completion time of the last job leaving the system, but in BPM problems the [C.sub.max] is completion time of the last batch leaving the system, because the completion time of all jobs in a batch is equal to the completion time of that batch.

Recently, batch processing machines problems have attracted many researchers. To minimize the makespan on a single BPM, Melouk et al. [17] provided simulated annealing (SA). For same environment, Damodaran et al. [6] and Husseinzadeh Kashan et al. [12] have proposed a genetic algorithm (GA) and two different genetic algorithms, respectively. Husseinzadeh Kashan and Karimi [10] proposed different versions of an ant colony framework for Scheduling a single batch-processing machine. Chou and Wang [4] for minimizing total weighted tardiness have provided GA and Chou [2] for minimizing the makespan have provided a joint genetic+dynamic programming algorithm. Chou et al [3] provided two versions of a hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. To minimize the maximum lateness on a batch processing machine, Wang and Uzsoy [20] have developed a GA.

To minimize makespan on parallel identical BPMs, Damodaran et al. [8] have been proposed a GA, Husseinzadeh Kashan et al. [11] proposed a HGA, Wang and Chou [19] employed GA and SA, Chang et al [1] provided a SA. To minimize makespan on same environment, Damodaran et al. [5] proposed a GA and the effectiveness of it compared with a Simulated Annealing approach, a Random Keys Genetic Algorithm, a Hybrid Genetic Heuristic and a commercial solver. To be minimize same criterion, Koh et al. [13] assumed incompatible job families with a common family processing time and proposed several heuristics and a GA. Malve and Uzsoy [15] proposed several GAs with incorporating some heuristics in previous works. They combined random key GA with some iterative improvement heuristics to minimize maximum lateness in same environment. Monch et al. [18] investigated two different approaches for scheduling jobs with incompatible job families and unequal ready times on parallel BPMs and genetic algorithms proposed to minimize total weighted tardiness.

Although the BPMs scheduling problems are considered by many researchers, but a flow shop with BPMs are seldom considered. Danneberg et al. [8] presented constructive algorithms to minimize makespan in a flow shop of BPMs. For a two batching machine flow shop, Damodaran and Srihari [7] have presented the only mixed integer formulations for the zero and infinite buffer capacity and Manjeshwar et al. [16] have proposed a SA for the case of the problem with infinite buffer capacity. To our knowledge, the only research that considers the flow shop scheduling with more than two BPMs (up 5 machines) was recently presented by Lei and Guo [14] that a variable neighborhood search (VNS) algorithm is designed to solve the problem. In this paper, we considered a BPMs problem in a flow shop environment in which a pre-known number of jobs are to be handled by many (three or more) batch-processing machines (henceforth referred to as FMBPM) based Damodaran and Srihari [8] which considered up two machines.

Since the flow shop scheduling in known to be a NP-Hard problem, the flow shop batch processing is also NP-Hard. As it can be seen, among metaheuristic algorithms only SA and VNS have been adapted for flow shop scheduling problems with batch processing machines which the former was applied for utmost two machines [16, 17] and the latter considered utmost five machines [13]. In the following, in order to prove the efficiency and effectiveness of our algorithms, the performance of the suggested algorithms is compared with some existing methods.

The remaining of the paper is organized as follows. In Section 2 the related assumptions, parameters and variables are introduced and a mixed integer programming model is suggested for the problem. Section 3 develops genetic algorithms. Experimental designs are described in Section 4 and experimental results and computational evaluations are described in Section 5. Section 6 reports concluding remarks and future research directions.

MATERIALS AND METHODS

Problem description:

As stated up, a many (three or more) batch processing machines in a flow shop is considered in this paper the objective is grouping jobs into batches, determining sequence and completion times of these batches on batch-processing machines in such a way that the makespan is minimized. To formulate this problem, the general assumptions, problem parameters and decision variables are listed below.

* Jobs cannot be added to or removed from a batch once processing has started.

* Preemption is not allowed.

* All jobs are available at time zero.

* Machine breakdowns are not considered.

* The job-processing times and job sizes are known with deterministic.

* The buffer between the two machines is infinite.

Min [C.sub.KM]

S.t. (1)

[[SIGMA].sub.b[member of]B][X.sub.jb] = 1, [for all]j [member of] J (2)

[[SIGMA].sub.j[member of]J] [S.sub.j][X.sub.jb] [less than or equal to] Cap, [for all]b [member of] B (3)

[P.sub.bm] [greater than or equal to] [P.sub.jm]. [X.sub.jb] , [for all]b [member of] B, m [member of] M, j [member of] J (4)

[summation over (k[member of]K)] [Z.sub.bkt] = 1, [for all]b [member of] B (5)

[summation over (b[member of]B)] [Z.sub.bk] = 1, [for all]k [member of] K (6)

[Q.sub.km] [greater than or equal to] [P.sub.bm] + L .([Z.sub.bk] -1), [for all]b e [member of]B, m e [member of]M , k [member of] K (7)

[C.sub.11] = [Q.sub.11] , (8)

[C.sub.1m] = [m.summation over (j)] [Q.sub.1j] , m [member of] M\{1} (9)

[C.sub.k1] = [k.summation over (j)] [Q.sub.j1], k [member of] K \{1} (10)

[C.sub.km] [greater than or equal to] [C.sub.k-1,m] + [Q.sub.km] , m [member of] M \{1}, k [member of] K \{1} (11)

[C.sub.km] [greater than or equal to] [C.sub.k,m-1] + [Q.sub.km] , m [member of] M \{1} , k [member of] K \{1} (12)

[X.sub.jb], [Z.sub.bk] binary , (13)

[C.sub.km] , [Q.sub.km] , [P.sub.bm] [greater than or equal to] 0. (14)

The objective (1) is to minimizing the completion time of the last batch on last machine or the makespan. Constraint (2) guarantees that exactly each job is assigned to one batch. Constraints (3) make sure that the sum of job sizes in a batch be less than machine capacity. Restrictions (4) state that the batch processing time is equal to the longest processing time of all the jobs in the batch. Limitations (5) and (6) guarantee that exactly each batch is assigned to one position in sequence and each position in sequence is assigned to one batch. Constraint

(7) determines the batch-processing time for the kth batch on machine m. Constraint (8) computes the completion time of the first batch in sequence on machine 1. Constraint (9) computes the completion time of the first batch in sequence on machine m and Constraint (10) computes completion time of the kth batch in sequence on machine 1. Constraint (11) and (12) Constraint (11) computes completion time of the kth batch in sequence on machine m. Constraint (13) enforce binary restrictions on [X.sub.jb] and Zbk decision variables and Finally constraint (14) enforce the non-negativity requirement on [C.sub.km] , [Q.sub.km] , and [P.sub.bm], dependent variables.

Metaheuristics for FMBPM:

While performance of a genetic algorithm depends on operators and the parameter settings, it depends on the most common encoding scheme for the batch processing machines is random keys (RK). In this work, regarding to problem which first-first (FF) heuristic [6] is applied to form the batches; we suggest the RK as follows. Assign job 1 to the lowest RK. Similarly for jobs 2 to n assign them to the lowest available RK. Afterwards, for batch formation, place the first job in the list in batch 1. Suppose we are placing job j, job j is placed in the lowest indexed batch if the job size does not exceed the remaining capacity of the batch (i.e., [S.sub.j] [less than or equal to] cap - [summation over (k[member of]J,k[not equal to]j)] [S.sub.j][X.sub.kb],). This process repeats to allocate all jobs to batches. Besides, the sequence of batches is

based on batch number, that is Batch 1, Batch 2, ... ,Batch B.

It is clear that the maximum possible number of batches formed will be the number of jobs. The process summarized in Fig. 1. The significant role of the initial solution on the quality of the final result of a search procedure has already been recognized and emphasized by many researchers in recent years. One of the traditional methods for initial solution is random generation which although the algorithm may lead to a satisfactory quality solution, while if be generated by an effective heuristic, will lead to a good and more reliable level of solution quality for a hard combinatorial problem. But as know research in FMBPM problems is very limited and no heuristic has been applied in initialization of a metaheuristic algorithm. On the other hand, NEH is a well- known and effective heuristic for minimizing the makespan in the classical flowshop. In this work, we investigate effect of the NEH heuristic as one of the individuals in the initial population on the quality of the final result of our algorithms.

[FIGURE 1 OMITTED]

Experimental design:

In order to evaluate the performance of the suggested algorithms, different sizes of test problems are generated as follows. In this section, we are going to generate the required data including number of jobs (n), number of machines (m), range of processing times (P) and size of jobs ([s.sub.j]). In order to determine number of jobs and number of machines in large size of problems, 6 levels for number of jobs i.e. n [member of]{15,20,30,50,100,150} and 6 levels for number of machines i.e. m [member of]{3,5,10,15,20,30} are considered that resulting in 10 combinations of m and n (Fbpm-L1~Fbpm-L10).

The processing times and size of jobs are generated randomly from uniform distributions between [1,30] and [1,10) respectively and the machine capacity (Cap) considered 10. Moreover, we consider n [member of] {3,4,5,7,8} and m [member of] {3,4} for small problems to be generated which The processing times and size of jobs are generated randomly from uniform distributions between [1,15] and [1,10) respectively (Fbpm-S1~Fbpm-S5), expected Fbpm-S1 that its Cap considered 5 and [s.sub.j] [member of] [1,5). Combinations of m and n are shown in Table 1.

Results:

In this section we aim to compare the performance of suggested GA with SA and the NEH heuristic as a well-known dispatching rule and a commercial solver. In order to make the comparison easier these algorithms, we use the relative percentage deviation (RPD) as a common performance measure as follows.

RPD = [Alg.sub.so1] - [Min.sub.so1]/[Min.sub.sol] x 100

where [Alg.sub.sol] is the objective function for attained by suggested algorithms and [Min.sub.sol] is the best obtained solution. By using this measure, a performance index between 0 and 100 is assigned to the each algorithm where a good solution has a RPD close to zero and a weak solution is a solution with RPD close to 100.

In order to verify the developed model and evaluate the performance of our algorithms against exact methods, a commercial optimization solver LINGO 11.0 is used to solve the problem instances. To this end, we execute the LINGO experiments for small instances and the resultant objectives are shown in Table 2. As can be seen in Table 2, the LINGO could find the best solution among other methods for just 2 data sets (Fbpm-s1 and Fbpm-s2). Besides, it could not reach to a solution for instance Fbpm-s5 after 10800 milliseconds computational time, while GA obtained the better solution than other algorithms in all instances up to 250 milliseconds.

As stated up, each size of the large test problem includes 5 generated test problems and four replications were performed for each trial to achieve the more reliable results. For more comprehensive comparisons, the results of the experiments were transformed into the RPD, averaged for test problems (20 data points per average) and are shown in Table 3. In this table, each row represents the average of results attained for 5 test problems considered in each size of large problem with four replications. As the comparison results presented in Table 3 reveal, our suggested algorithms outperform for large instances. This table shows the high performance of GA (RPD = 0.0351 with respect to SA and NEH. The worst performing algorithm is the NEH heuristic (RPD = 0.1279).

To evaluate the robustness of the algorithms in different situations, a means plot for the interaction between the different algorithms in (1) different size of problems (2) number of batch processing machines and (3) number of jobs are shown in Figs. 2-4 respectively.

[FIGURE 2 OMITTED]

As can be seen in Fig. 2, GA exhibits robust performance regarding increased size of problem and outperforms the other algorithms in all cases.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

There is a clear trend that increasing the number of batch-processing machines and number of jobs results in better performance of the GA. Other notable occasion is improving the performance of NEH heuristic regarding increased size of problem, number of the jobs and number of the batch- processing machines.

Conclusions:

This paper presents a permutation flow shop batch processing machines scheduling problem in which a batch of jobs can be simultaneously processed on machines. In classical flow shop scheduling problems, the machines are limited to process only one job at a time, while in many manufacturing environments a machine can simultaneously process several jobs as long as the total sizes of jobs in a batch do not exceed the machine capacity. In order to minimize the makespan, a mixed integer programming model is proposed to formulate the problem considered. This class of problems is NP-hard for makespan objective. Furthermore, by this method explored which the NEH heuristic as one of the individuals in the initial solution have a good effect on the quality of the final result of all algorithms in FMBPM. In order to show the effectiveness of our algorithms, a set of benchmark ranging from 3 to 150 jobs and 3 to 30 batch processing machines are generated that contain 5 random small problems and 10 sizes of large problems. Each size includes 5 generated test problems and four replications were performed for each trial. The obtained results revealed that the GA performs very well in terms of both efficiency and effectiveness. Regarding increased the size of problem, the number of BPMs and number of jobs results in better performance of the GA.

As a direction for future research, it could be considered to extend the batch processing model developed in this paper to the other complex environments like job shops and open shops or even other variants of flow shop scheduling.

ARTICLE INFO

Article history:

Received 12 October 2014

Received in revised form 26 December 2014

Accepted 1 January 2015

Available online 20 February 2015

ACKNOWLEDGEMENT

This study was supported by Islamic Azad University, shoushtar Branch. The first author is grateful for this financial support.

REFERENCES

[1] Chang, P.Y., P. Damodaran and S. Melouk, 2004. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 42: 4211-4220.

[2] Chou, F.D., 2007. A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion. International Journal of Advance Manufacturing Technology, 35: 587- 595.

[3] Chou, F.D., P.C. Chang and H.M. Wang, 2006. A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. International Journal of Advanced Manufacturing Technology, 31: 350-359.

[4] Chou, F.D. and H.M. Wang, 2008. Scheduling for a single semiconductor batch- processing machine to minimize total weighted tardiness. Journal of the Chinese Institute of Industrial Engineers, 25: 136-147.

[5] Damodaran, P., N.S. Hirani and M.C. Velez-Gallego, 2009. Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithm. European Journal of Industrial Engineering, 3: 187-206.

[6] Damodaran, P., P.K. Manjeshwar and K. Srihari, 2006. Minimizing makespan on a batch processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 103: 882-891.

[7] Damodaran, P. and K. Srihari, 2004. Mixed integer formulation to minimize makespan in flow shop with batch processing machines, Mathematical and Computer Modeling, 40: 1465-1472.

[8] Damodaran, P.K. and K. Srihari, 2009. Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing. Robotics and Computer-Integrated Manufacturing, 25: 667- 679.

[9] Danneberg, D., T. Tautenhahn and F. Werner, 1999. A comparison of heuristic algorithms for flow shop scheduling problems with set up times and limited batch size. Mathematical and Computer Modeling, 29: 101-126.

[10] Husseinzadeh Kashan, A. and B. Karimi, 2008. Scheduling a single batch- processing machine with arbitrary job sizes and incompatible job families: an ant colony framework. Journal of the Operational Research Society, 59: 1269-1280.

[11] Husseinzadeh Kashan, A., B. Karimi and M. Jenabi, 2008. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35: 10841098.

[12] Husseinzadeh Kashan, A., B. Karimi and F. Jolai, 2006. Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes. International Journal of Production Research, 44: 2337-2360.

[13] Koh, S.G., P.H. Koo, J.W. Ha and W.S. Lee, 2004. Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families. International Journal of Production Research, 42: 40914107.

[14] Lei, D. and X.P. Guo, 2011. Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines. International Journal of Production Research, 49: 519-529.

[15] Malve, S. and R. Uzsoy, 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: 3016-3028.

[16] Manjeshwar, P.K., P. Damodaran and K. Srihari, 2011. Genetic algorithms for minimizing makespan in a flow shop with two capacitated batch processing machines. International Journal of Advanced Manufacturing T echnology, 55: 1171-1182.

[17] Melouk, S., P. Damodaran and P.Y. Cheng, 2004. Minimizing make span for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 87: 141-147.

[18] Monch, L., H. Balasubramanian, J.W. Fowler and M. Pfund, 2005. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers and Operations Research, 32: 2731-2750.

[19] Wang, H. and F. Chou, 2010. Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications, 37: 1510-1521.

[20] Wang, C. and R. Uzsoy, 2002. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers & Operations Research, 29: 1621-1640.

(1) Abbas Esmaeili, (2) Saber Molla-Alizadeh-Zavardehi, (3) Ali Mahmoodirad, (4) Sadegh Niroomand

(1) Department of Management, Shoushtar Branch, Islamic Azad University, Shoushtar, Iran

(2) Department of Industrial Engineering, Masjed Soleiman Branch, Islamic Azad University, Masjed- Soleiman, Iran

(3) Department of Mathematics, Masjed-Soleiman Branch, Islamic Azad University, Masjed-Soleiman, Iran

(4) Department of Industrial Engineering, Eastern Mediterranean University, Famagusta, North Cyprus, Turkey

Corresponding Author: Ali Mahmoodirad, Department of Mathematics, Masjed- Soleiman Branch, Islamic Azad University, Masjed- Soleiman, Iran.

Tel: +989112138385, E-mail: alimahmoodirad@yahoo.com

A batch processing machine (BPM) is one in which can simultaneously process several jobs in a batch. They are commonly used in heat-treating ovens, semiconductor burn- in operations, chemical processes performed in tanks or kilns, testing process of electrical circuits, wafer fabrication process, pharmaceutical and construction materials industries, to name a few. The formal description to the flow shop with batch processing machines considered in this paper is as follows. There are N jobs available that each job j has processing time Pjm on batch-processing machine m. Each machine has a capacity equal to Cap and can process a batch only when the total size of all the jobs in a batch does not exceed its capacity. All the jobs have to be grouped into batches and these batches are processed in the same order, on all the machines. Thus the problem considered here is a permutation flow shop problem, i.e., all batches are processed on each in a fixed process flow.

The processing time of batch b (Bb) on machine m which is denoted by [P.sub.bm] is the longest processing times among all the jobs in that batch. Regarding this description, two important and distinct decisions, but dependent, made on BPM problems are: first, grouping jobs into batches, and second, scheduling the batches to improve a performance measure. A minimum makespan ([C.sub.max]) usually implies a high utilization of the machine(s). Therefore, reducing [C.sub.max] should also lead to a higher throughput rate. This concern led us to consider the makespan performance measure as the scheduling objective. In theory of scheduling, [C.sub.max] is equivalent to the completion time of the last job leaving the system, but in BPM problems the [C.sub.max] is completion time of the last batch leaving the system, because the completion time of all jobs in a batch is equal to the completion time of that batch.

Recently, batch processing machines problems have attracted many researchers. To minimize the makespan on a single BPM, Melouk et al. [17] provided simulated annealing (SA). For same environment, Damodaran et al. [6] and Husseinzadeh Kashan et al. [12] have proposed a genetic algorithm (GA) and two different genetic algorithms, respectively. Husseinzadeh Kashan and Karimi [10] proposed different versions of an ant colony framework for Scheduling a single batch-processing machine. Chou and Wang [4] for minimizing total weighted tardiness have provided GA and Chou [2] for minimizing the makespan have provided a joint genetic+dynamic programming algorithm. Chou et al [3] provided two versions of a hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. To minimize the maximum lateness on a batch processing machine, Wang and Uzsoy [20] have developed a GA.

To minimize makespan on parallel identical BPMs, Damodaran et al. [8] have been proposed a GA, Husseinzadeh Kashan et al. [11] proposed a HGA, Wang and Chou [19] employed GA and SA, Chang et al [1] provided a SA. To minimize makespan on same environment, Damodaran et al. [5] proposed a GA and the effectiveness of it compared with a Simulated Annealing approach, a Random Keys Genetic Algorithm, a Hybrid Genetic Heuristic and a commercial solver. To be minimize same criterion, Koh et al. [13] assumed incompatible job families with a common family processing time and proposed several heuristics and a GA. Malve and Uzsoy [15] proposed several GAs with incorporating some heuristics in previous works. They combined random key GA with some iterative improvement heuristics to minimize maximum lateness in same environment. Monch et al. [18] investigated two different approaches for scheduling jobs with incompatible job families and unequal ready times on parallel BPMs and genetic algorithms proposed to minimize total weighted tardiness.

Although the BPMs scheduling problems are considered by many researchers, but a flow shop with BPMs are seldom considered. Danneberg et al. [8] presented constructive algorithms to minimize makespan in a flow shop of BPMs. For a two batching machine flow shop, Damodaran and Srihari [7] have presented the only mixed integer formulations for the zero and infinite buffer capacity and Manjeshwar et al. [16] have proposed a SA for the case of the problem with infinite buffer capacity. To our knowledge, the only research that considers the flow shop scheduling with more than two BPMs (up 5 machines) was recently presented by Lei and Guo [14] that a variable neighborhood search (VNS) algorithm is designed to solve the problem. In this paper, we considered a BPMs problem in a flow shop environment in which a pre-known number of jobs are to be handled by many (three or more) batch-processing machines (henceforth referred to as FMBPM) based Damodaran and Srihari [8] which considered up two machines.

Since the flow shop scheduling in known to be a NP-Hard problem, the flow shop batch processing is also NP-Hard. As it can be seen, among metaheuristic algorithms only SA and VNS have been adapted for flow shop scheduling problems with batch processing machines which the former was applied for utmost two machines [16, 17] and the latter considered utmost five machines [13]. In the following, in order to prove the efficiency and effectiveness of our algorithms, the performance of the suggested algorithms is compared with some existing methods.

The remaining of the paper is organized as follows. In Section 2 the related assumptions, parameters and variables are introduced and a mixed integer programming model is suggested for the problem. Section 3 develops genetic algorithms. Experimental designs are described in Section 4 and experimental results and computational evaluations are described in Section 5. Section 6 reports concluding remarks and future research directions.

MATERIALS AND METHODS

Problem description:

As stated up, a many (three or more) batch processing machines in a flow shop is considered in this paper the objective is grouping jobs into batches, determining sequence and completion times of these batches on batch-processing machines in such a way that the makespan is minimized. To formulate this problem, the general assumptions, problem parameters and decision variables are listed below.

* Jobs cannot be added to or removed from a batch once processing has started.

* Preemption is not allowed.

* All jobs are available at time zero.

* Machine breakdowns are not considered.

* The job-processing times and job sizes are known with deterministic.

* The buffer between the two machines is infinite.

Sets: J Jobs which j [member of] J M Machines which m [member of] M B Batches which b [member of] B K Positions in sequence which k [member of] K Parameters: [P.sub.jm] Processing time of job j on machine m [S.sub.j] Size of job j Cap Capacity of machine L Positive large integer Decision variables: [X.sub.jb] A binary variable indicates the assignment of job j to the batch b [Z.sub.bk] A binary variable indicates whether the batch b is assigned to position k Dependent variables: [P.sub.bm] processing time of batch b on machine m [C.sub.km] completion time of the kth batch on machine m [Q.sub.km] processing time of the kth batch in sequence on machine m [C.sub.km] completion time of the last batch on last machine (makespan)

Min [C.sub.KM]

S.t. (1)

[[SIGMA].sub.b[member of]B][X.sub.jb] = 1, [for all]j [member of] J (2)

[[SIGMA].sub.j[member of]J] [S.sub.j][X.sub.jb] [less than or equal to] Cap, [for all]b [member of] B (3)

[P.sub.bm] [greater than or equal to] [P.sub.jm]. [X.sub.jb] , [for all]b [member of] B, m [member of] M, j [member of] J (4)

[summation over (k[member of]K)] [Z.sub.bkt] = 1, [for all]b [member of] B (5)

[summation over (b[member of]B)] [Z.sub.bk] = 1, [for all]k [member of] K (6)

[Q.sub.km] [greater than or equal to] [P.sub.bm] + L .([Z.sub.bk] -1), [for all]b e [member of]B, m e [member of]M , k [member of] K (7)

[C.sub.11] = [Q.sub.11] , (8)

[C.sub.1m] = [m.summation over (j)] [Q.sub.1j] , m [member of] M\{1} (9)

[C.sub.k1] = [k.summation over (j)] [Q.sub.j1], k [member of] K \{1} (10)

[C.sub.km] [greater than or equal to] [C.sub.k-1,m] + [Q.sub.km] , m [member of] M \{1}, k [member of] K \{1} (11)

[C.sub.km] [greater than or equal to] [C.sub.k,m-1] + [Q.sub.km] , m [member of] M \{1} , k [member of] K \{1} (12)

[X.sub.jb], [Z.sub.bk] binary , (13)

[C.sub.km] , [Q.sub.km] , [P.sub.bm] [greater than or equal to] 0. (14)

The objective (1) is to minimizing the completion time of the last batch on last machine or the makespan. Constraint (2) guarantees that exactly each job is assigned to one batch. Constraints (3) make sure that the sum of job sizes in a batch be less than machine capacity. Restrictions (4) state that the batch processing time is equal to the longest processing time of all the jobs in the batch. Limitations (5) and (6) guarantee that exactly each batch is assigned to one position in sequence and each position in sequence is assigned to one batch. Constraint

(7) determines the batch-processing time for the kth batch on machine m. Constraint (8) computes the completion time of the first batch in sequence on machine 1. Constraint (9) computes the completion time of the first batch in sequence on machine m and Constraint (10) computes completion time of the kth batch in sequence on machine 1. Constraint (11) and (12) Constraint (11) computes completion time of the kth batch in sequence on machine m. Constraint (13) enforce binary restrictions on [X.sub.jb] and Zbk decision variables and Finally constraint (14) enforce the non-negativity requirement on [C.sub.km] , [Q.sub.km] , and [P.sub.bm], dependent variables.

Metaheuristics for FMBPM:

While performance of a genetic algorithm depends on operators and the parameter settings, it depends on the most common encoding scheme for the batch processing machines is random keys (RK). In this work, regarding to problem which first-first (FF) heuristic [6] is applied to form the batches; we suggest the RK as follows. Assign job 1 to the lowest RK. Similarly for jobs 2 to n assign them to the lowest available RK. Afterwards, for batch formation, place the first job in the list in batch 1. Suppose we are placing job j, job j is placed in the lowest indexed batch if the job size does not exceed the remaining capacity of the batch (i.e., [S.sub.j] [less than or equal to] cap - [summation over (k[member of]J,k[not equal to]j)] [S.sub.j][X.sub.kb],). This process repeats to allocate all jobs to batches. Besides, the sequence of batches is

based on batch number, that is Batch 1, Batch 2, ... ,Batch B.

It is clear that the maximum possible number of batches formed will be the number of jobs. The process summarized in Fig. 1. The significant role of the initial solution on the quality of the final result of a search procedure has already been recognized and emphasized by many researchers in recent years. One of the traditional methods for initial solution is random generation which although the algorithm may lead to a satisfactory quality solution, while if be generated by an effective heuristic, will lead to a good and more reliable level of solution quality for a hard combinatorial problem. But as know research in FMBPM problems is very limited and no heuristic has been applied in initialization of a metaheuristic algorithm. On the other hand, NEH is a well- known and effective heuristic for minimizing the makespan in the classical flowshop. In this work, we investigate effect of the NEH heuristic as one of the individuals in the initial population on the quality of the final result of our algorithms.

Step 1: Problem datas RKs 0.23 0.18 0.87 0.36 0.76 0.46 Job number J1 J2 J3 J4 J5 J6 Job size 3 5 3 1 9 1 Pj1 14 6 17 25 9 8 Pj2 3 24 15 7 17 1 RKs 0.53 0.93 0.38 0.84 Job number J7 J8 J9 J10 Job size 2 8 4 2 Pj1 23 19 17 12 Pj2 9 11 21 14 Step 2: Sequencing jobs based on RKs RKs 0.23 0.18 0.87 0.36 0.76 Job sequence J2 J1 J9 J3 J7 RKs 0.46 0.53 0.93 0.38 0.84 Job sequence J5 J6 J10 J4 J8 Step 3:.Forming and sequencing batches Based on the FF heuristic (Cap=10) Batch processing time Formed batches Jobs in the batch M1 M2 M3 B1 J2 J1 J7 23 24 19 B2 J9 J3 J6 J10 17 21 23 B3 J5 9 17 9 B4 J4 J8 25 11 13 Step 5: Computing Makespan. Batch sequence B1 B2 B3 B4

[FIGURE 1 OMITTED]

Experimental design:

In order to evaluate the performance of the suggested algorithms, different sizes of test problems are generated as follows. In this section, we are going to generate the required data including number of jobs (n), number of machines (m), range of processing times (P) and size of jobs ([s.sub.j]). In order to determine number of jobs and number of machines in large size of problems, 6 levels for number of jobs i.e. n [member of]{15,20,30,50,100,150} and 6 levels for number of machines i.e. m [member of]{3,5,10,15,20,30} are considered that resulting in 10 combinations of m and n (Fbpm-L1~Fbpm-L10).

The processing times and size of jobs are generated randomly from uniform distributions between [1,30] and [1,10) respectively and the machine capacity (Cap) considered 10. Moreover, we consider n [member of] {3,4,5,7,8} and m [member of] {3,4} for small problems to be generated which The processing times and size of jobs are generated randomly from uniform distributions between [1,15] and [1,10) respectively (Fbpm-S1~Fbpm-S5), expected Fbpm-S1 that its Cap considered 5 and [s.sub.j] [member of] [1,5). Combinations of m and n are shown in Table 1.

Results:

In this section we aim to compare the performance of suggested GA with SA and the NEH heuristic as a well-known dispatching rule and a commercial solver. In order to make the comparison easier these algorithms, we use the relative percentage deviation (RPD) as a common performance measure as follows.

RPD = [Alg.sub.so1] - [Min.sub.so1]/[Min.sub.sol] x 100

where [Alg.sub.sol] is the objective function for attained by suggested algorithms and [Min.sub.sol] is the best obtained solution. By using this measure, a performance index between 0 and 100 is assigned to the each algorithm where a good solution has a RPD close to zero and a weak solution is a solution with RPD close to 100.

In order to verify the developed model and evaluate the performance of our algorithms against exact methods, a commercial optimization solver LINGO 11.0 is used to solve the problem instances. To this end, we execute the LINGO experiments for small instances and the resultant objectives are shown in Table 2. As can be seen in Table 2, the LINGO could find the best solution among other methods for just 2 data sets (Fbpm-s1 and Fbpm-s2). Besides, it could not reach to a solution for instance Fbpm-s5 after 10800 milliseconds computational time, while GA obtained the better solution than other algorithms in all instances up to 250 milliseconds.

As stated up, each size of the large test problem includes 5 generated test problems and four replications were performed for each trial to achieve the more reliable results. For more comprehensive comparisons, the results of the experiments were transformed into the RPD, averaged for test problems (20 data points per average) and are shown in Table 3. In this table, each row represents the average of results attained for 5 test problems considered in each size of large problem with four replications. As the comparison results presented in Table 3 reveal, our suggested algorithms outperform for large instances. This table shows the high performance of GA (RPD = 0.0351 with respect to SA and NEH. The worst performing algorithm is the NEH heuristic (RPD = 0.1279).

To evaluate the robustness of the algorithms in different situations, a means plot for the interaction between the different algorithms in (1) different size of problems (2) number of batch processing machines and (3) number of jobs are shown in Figs. 2-4 respectively.

[FIGURE 2 OMITTED]

As can be seen in Fig. 2, GA exhibits robust performance regarding increased size of problem and outperforms the other algorithms in all cases.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

There is a clear trend that increasing the number of batch-processing machines and number of jobs results in better performance of the GA. Other notable occasion is improving the performance of NEH heuristic regarding increased size of problem, number of the jobs and number of the batch- processing machines.

Conclusions:

This paper presents a permutation flow shop batch processing machines scheduling problem in which a batch of jobs can be simultaneously processed on machines. In classical flow shop scheduling problems, the machines are limited to process only one job at a time, while in many manufacturing environments a machine can simultaneously process several jobs as long as the total sizes of jobs in a batch do not exceed the machine capacity. In order to minimize the makespan, a mixed integer programming model is proposed to formulate the problem considered. This class of problems is NP-hard for makespan objective. Furthermore, by this method explored which the NEH heuristic as one of the individuals in the initial solution have a good effect on the quality of the final result of all algorithms in FMBPM. In order to show the effectiveness of our algorithms, a set of benchmark ranging from 3 to 150 jobs and 3 to 30 batch processing machines are generated that contain 5 random small problems and 10 sizes of large problems. Each size includes 5 generated test problems and four replications were performed for each trial. The obtained results revealed that the GA performs very well in terms of both efficiency and effectiveness. Regarding increased the size of problem, the number of BPMs and number of jobs results in better performance of the GA.

As a direction for future research, it could be considered to extend the batch processing model developed in this paper to the other complex environments like job shops and open shops or even other variants of flow shop scheduling.

ARTICLE INFO

Article history:

Received 12 October 2014

Received in revised form 26 December 2014

Accepted 1 January 2015

Available online 20 February 2015

ACKNOWLEDGEMENT

This study was supported by Islamic Azad University, shoushtar Branch. The first author is grateful for this financial support.

REFERENCES

[1] Chang, P.Y., P. Damodaran and S. Melouk, 2004. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 42: 4211-4220.

[2] Chou, F.D., 2007. A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion. International Journal of Advance Manufacturing Technology, 35: 587- 595.

[3] Chou, F.D., P.C. Chang and H.M. Wang, 2006. A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. International Journal of Advanced Manufacturing Technology, 31: 350-359.

[4] Chou, F.D. and H.M. Wang, 2008. Scheduling for a single semiconductor batch- processing machine to minimize total weighted tardiness. Journal of the Chinese Institute of Industrial Engineers, 25: 136-147.

[5] Damodaran, P., N.S. Hirani and M.C. Velez-Gallego, 2009. Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithm. European Journal of Industrial Engineering, 3: 187-206.

[6] Damodaran, P., P.K. Manjeshwar and K. Srihari, 2006. Minimizing makespan on a batch processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 103: 882-891.

[7] Damodaran, P. and K. Srihari, 2004. Mixed integer formulation to minimize makespan in flow shop with batch processing machines, Mathematical and Computer Modeling, 40: 1465-1472.

[8] Damodaran, P.K. and K. Srihari, 2009. Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing. Robotics and Computer-Integrated Manufacturing, 25: 667- 679.

[9] Danneberg, D., T. Tautenhahn and F. Werner, 1999. A comparison of heuristic algorithms for flow shop scheduling problems with set up times and limited batch size. Mathematical and Computer Modeling, 29: 101-126.

[10] Husseinzadeh Kashan, A. and B. Karimi, 2008. Scheduling a single batch- processing machine with arbitrary job sizes and incompatible job families: an ant colony framework. Journal of the Operational Research Society, 59: 1269-1280.

[11] Husseinzadeh Kashan, A., B. Karimi and M. Jenabi, 2008. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35: 10841098.

[12] Husseinzadeh Kashan, A., B. Karimi and F. Jolai, 2006. Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes. International Journal of Production Research, 44: 2337-2360.

[13] Koh, S.G., P.H. Koo, J.W. Ha and W.S. Lee, 2004. Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families. International Journal of Production Research, 42: 40914107.

[14] Lei, D. and X.P. Guo, 2011. Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines. International Journal of Production Research, 49: 519-529.

[15] Malve, S. and R. Uzsoy, 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: 3016-3028.

[16] Manjeshwar, P.K., P. Damodaran and K. Srihari, 2011. Genetic algorithms for minimizing makespan in a flow shop with two capacitated batch processing machines. International Journal of Advanced Manufacturing T echnology, 55: 1171-1182.

[17] Melouk, S., P. Damodaran and P.Y. Cheng, 2004. Minimizing make span for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 87: 141-147.

[18] Monch, L., H. Balasubramanian, J.W. Fowler and M. Pfund, 2005. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers and Operations Research, 32: 2731-2750.

[19] Wang, H. and F. Chou, 2010. Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications, 37: 1510-1521.

[20] Wang, C. and R. Uzsoy, 2002. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers & Operations Research, 29: 1621-1640.

(1) Abbas Esmaeili, (2) Saber Molla-Alizadeh-Zavardehi, (3) Ali Mahmoodirad, (4) Sadegh Niroomand

(1) Department of Management, Shoushtar Branch, Islamic Azad University, Shoushtar, Iran

(2) Department of Industrial Engineering, Masjed Soleiman Branch, Islamic Azad University, Masjed- Soleiman, Iran

(3) Department of Mathematics, Masjed-Soleiman Branch, Islamic Azad University, Masjed-Soleiman, Iran

(4) Department of Industrial Engineering, Eastern Mediterranean University, Famagusta, North Cyprus, Turkey

Corresponding Author: Ali Mahmoodirad, Department of Mathematics, Masjed- Soleiman Branch, Islamic Azad University, Masjed- Soleiman, Iran.

Tel: +989112138385, E-mail: alimahmoodirad@yahoo.com

Table 1. The descriptions on the randomly generated problems Problem m n Problem m n Problem m n Fbpm-S1 3 4 Fbpm-L1 3 15 Fbpm-L6 15 50 Fbpm-S2 3 4 Fbpm-L2 5 20 Fbpm-L7 15 100 Fbpm-S3 3 7 Fbpm-L3 5 30 Fbpm-L8 20 100 Fbpm-S4 4 5 Fbpm-L4 10 30 Fbpm-L9 20 150 Fbpm-S5 4 8 Fbpm-L5 10 50 Fbpm-L10 30 150 Table 2: Comparison of algorithms in small instances. LINGO GA problem [C.sub.max] Time [C.sub.max] Time Fbpm-S1 42 71 42 < 64 Fbpm-S2 40 575 40 < 72 Fbpm-S3 64 3749 55 < 130 Fbpm-S4 73 6941 48 < 160 Fbpm-S5 -- >10800 59 < 250 Table 3: Average relative percentage deviation for the algorithms. Algorithms Problem NEH SA GA Fbpm-L1 0.1718 0.0370 0.0376 Fbpm-L2 0.1738 0.0376 0.0369 Fbpm-L3 0.1738 0.0576 0.0442 Fbpm-L4 0.1342 0.0430 0.0253 Fbpm-L5 0.1292 0.0575 0.0356 Fbpm-L6 0.1168 0.0644 0.0348 Fbpm-L7 0.1113 0.0543 0.0384 Fbpm-L8 0.0976 0.0602 0.0344 Fbpm-L9 0.0871 0.0575 0.0376 Fbpm-L10 0.0778 0.0494 0.0260 Average 0.1279 0.05185 0.0351

Printer friendly Cite/link Email Feedback | |

Author: | Esmaeili, Abbas; Molla-Alizadeh-Zavardehi, Saber; Mahmoodirad, Ali; Niroomand, Sadegh |
---|---|

Publication: | Advances in Environmental Biology |

Article Type: | Report |

Date: | Feb 1, 2015 |

Words: | 4097 |

Previous Article: | Study of the effect of compact fluorescent lamp on the acetaminophen degradation. |

Next Article: | Water quality improvement of Hendijan River by use of Mike 11 model. |

Topics: |