Printer Friendly

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.
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
COPYRIGHT 2015 American-Eurasian Network for Scientific Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
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:

Terms of use | Copyright © 2017 Farlex, Inc. | Feedback | For webmasters