Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.16 No.2 pp.265-270
DOI : https://doi.org/10.7232/iems.2017.16.2.265

A Heuristic Method for Solving Bi-Objective Two-Stage Hybrid Flow Shop Scheduling Problem

Kamran Mehrdoust Shahrestani*, Parviz Fattahi, Maryam Hamedi
Department of Industrial Engineering, Payame Noor University, Tehran, Iran
Department of Industrial Engineering, Boo Ali Sina University, Hamedan, Iran
Department of Industrial Engineering, Payame Noor University, Tehran, Iran
Corresponding Author, kamranmehrdoost@pnu.ac.ir
February 28, 2017 April 15, 2017 April 24, 2017

ABSTRACT

Hybrid flow shop problems are the most widely used in scheduling problems. A two-stage hybrid flow shop can be considered as part of a larger problem we have studied the scheduling of a two-stage hybrid flow shop problem which contains one machine at the first stage and two machines at the second stage with two objectives, the average flow time (F) and the average tardiness (T). In this paper a heuristic method has been introduced and it has been compared to a multi-objective decision making (lexicography) using simulated annealing (SA) Algorithm on both objective. Eventually, obtained solutions have been solved by simple additive weighting (SAW) method. The weight of criteria have been obtained based on the Shannon Entropy. The result indicated that the proposed heuristic method solution in 90.4% problems has led to better than solutions based on SA Algorithm. The solutions obtained out of 500 problems in heuristic method is 15.04% better than the solutions obtained according to SA Algorithm. And also in heuristic method, the obtained solutions were 58 times faster than SA Algorithm method


초록


    1.INTRODUCTION

    Hybrid flow shop scheduling is the most widely used scheduling problems. A hybrid flow shop consists of a series of stages or production workshops; each stage contains some machines (sources). There may be one machine on some stages but since this system is called hybrid flow shop system, there should be some parallel machines on at least one stage Ghomi and Zandieh (2002).

    The hybrid flow shop problem is an extended mode of two particular types of scheduling which are known as flow shop scheduling and parallel machines problems. It consists of a series of production steps each of which contains several operating parallel machines. The flow of products in production system is the same and single directed. Each task is processed by a machine in each stage and the machines in each stage could have different processing speed. Therefore, determining the order of the tasks to be processed in system is not the only objective, but to setting priorities and order of processing tasks, assigning proper task to each of the parallel machines to achieve efficient criteria is considered too (Gholami and Moosaloo, 2011). In Figure 1 a hybrid flow shop is shown which contains one machine at first stage and two machines at second stage.

    The issue studied in this paper is to schedule a twostage hybrid flow shop which contains one machine at first stage and two parallel machines with different processing times at second stage (Figure 1). some widely used cases of this problem can be mentioned in two-stage production systems such as knitting factories, plastic injection and also some industrial productions like forging, casting and machinery.

    The objective is to choose an appropriate order for tasks to be processed without any constraints in number of tasks on the machine of first stage, then to assign each first-staged processed task to one of the machines of second stage; as a result, the defined criteria would be optimized for evaluating efficiency of scheduling.

    The purpose of the function in most scheduling problems is to minimize the maximum completion time (Makespan). In spite of the importance of scheduling problems in multi-criteria hybrid flow shop, studies in this field are less than those in other scheduling fields (Taghaddosi and Khoshalhan, 2010; Momenzadeh et al., 2017).

    Therefore, in this study, two criteria, the average tardiness (T ) and the average flow time of tasks (F) are considered. The goal is to choose the order of processing tasks on two-stage machines which leads to minimization of both criteria at the same time.

    2.THE LITERATURE REVIEW

    Two-stage (HFS) scheduling is said to be a kind of flow shop which contains more than one machine on at least one stage for processing the tasks. Gupta indicated that HFS problem with two-stage processing is a NP-hard problem even if one of the stages contains two machines and another stage contains one machine (Gupta, 1988). Hybrid flow shop problems can be classified and studied from different points of views. Ribas et al. (2010) studied and classified the hybrid flow shop problems based on the type of machine which was used (Ribas et al., 2010). They classified hybrid flow shop problems into three classes of unrelated, uniform and identical parallel machines. Ruiz and Rodriguez classified hybrid flow shop problems into three classes of two-stage, three-stage and K-stage. They have also studied a great number of hybrid flow shop essays in terms of scheduling; and according to the method used in problem solving; they classified them in three distinct classes: 1-using the exact algorithm. 2- Using the heuristic algorithm and dispatching rules. 3- Using the meta-heuristic algorithm (Ruiz et al., 2010).

    Since the exact algorithms due to complexity and time consuming problems are not able to solve all hybrid flow shop problems, the heuristic and meta-heuristic algorithms have been developed in this field. Choong et al. (2011) also studied some meta-heuristic methods which can be used in hybrid flow shop, they found out that the SA and TS algorithms are the most widely used metaheuristic algorithms in the field of hybrid flow shop.

    In HFS problems, the easiest plot is, considering only two-stage in which the first stage contains one machine and the second one contains two machines. Wang and Liu (2013) studied a set of n independent tasks in order to minimize the maximum completion time in hybrid flow shop areas, using one machine at first stage and two or some dedicated machines at second stage provided that the specified operation of each task is done initially on machine of first stage then on its dedicated machine at second stage. They proposed a heuristic method according to branch and bound and TS and SA algorithms Rezaeian et al. (2013) have extended the wang and Liu’s proposed method for assembled hybrid flow shop and they presented a linear arrangement model in order to minimize the maximum completion time (Makespan).

    Yang (2015) has also studied this problem but with two dedicated machines at first stage and one machine at second stage. Tang showed the complexity of this issue meanwhile offered two simple heuristic methods for solving this problem and also Tang compared their worst case solutions.

    Many studies have been done on the topic of hybrid flow shop scheduling. Some of them, were considered on kind of parallel machines as uniform machines, dedicated machines and unrelated machines (Linn and Zhang, 1999). Others Due to the setup times and considered Setup times independent or dependent on the operations (Morais et al., 2013). They were considered setup time in processing time or ignore it. Fuzzy evaluation parameters and criteria have also been considered in recent years. As fuzzy process times, fuzzy due dates and Fuzzy Idle (Kumar et al., 2010; Momenzadeh, et al., 2012).

    3.METHODOLOGY

    In this paper, it has been tried to study Wang and Liu (2013) two-stage problem in hybrid flow shop field with one machine at first stage and two uniform machines at second stage. The aim is to obtain two objective at the same time, minimize the average tardiness (T) and minimize the average flow time (F). To do this, multiobjective decision making technique with lexicography (absolute priority) is used and also SAW multi attribute decision making with Shannon entropy weighting method are used. At the beginning, the problem is investigated as a single objective by one criterion, and the best solution is chosen by the SA meta-heuristic algorithm then, the obtained solution is applied in the problem as a constraint and the problem will be investigated again by another objective. Since the relative priority of criteria is not assigned, this procedure will be done twice, each time with one objective; therefore, there are two distinct solutions for the problem (Figure 2). Also a heuristic algorithm is developed for solving this problem which is called a third solution of this problem. In the end, the three solutions will be evaluated with two criteria of minimizing the average tardiness (T) and the average flow time (F) by using the SAW method. The importance of each criterion is determined by Shannon entropy method. Some advantages of this study are 1) Investigating the problem as two criteria, 2) Using uniform machines at second stage and 3) Using two multi criteria decision making techniques consecutively.

    In this problem, all tasks are available at time zero. At first, each task should be processed at first stage then at the second stage. Setup time and transportation time are considered in process time. All machines are continually available and breaking time due to machine destruction, failure or maintenance is not defined. Stopping the tasks is not allowed and no task can be processed on several machines at the same time.

    3.1.Problem Solving Approach

    First, a heuristic method is developed to solve this problem; the obtained result is compared with two codes written by MATLAB software. These two codes are based on the SA algorithm and lexicography (absolute priority) method that each of them firstly, minimizes one criterion and then with achieving the first criterion, minimizes the second criterion too. in second step, three algorithms data (H, SA F, SAT) create a decision matrix with two criteria which are, minimizing the average tardiness (T) and minimizing the average flow time (F). Eventually, the most appropriate solution is chosen by means of simple additive weighting (SAW) and the Shannon entropy weighting method.

    3.2.Proposed Simulated Annealing (SA) Algorithm in this Problem

    Simulated Annealing (SA) is a search technique that can be used to seek good solutions for various combinatorial problems. It is a stochastic search method to find an acceptable solution (Fattahi, 2009; Shen et al., 2017).

    The algorithm consist of four main steps:

    • (i) Configurations

    • (ii) Re configuration technique

    • (iii) Cost function

    • (iv) Cooling schedule

    The SA algorithm starts with the initial solution then it goes toward the neighborhood solutions in a reaping loop, if the neighborhood solution is better than the primary solution, the algorithm will consider it as current solution, otherwise; the algorithm with the probability exp(-ΔE/T) will consider it as a current solution. In this formula the ΔE stands for the difference between current solution and neighborhood solution and T stands for temperature parameter. Several iterations are done in each temperature and then the temperature is reduced gradually. In first steps with higher temperature, it is more likely to get the worse solutions and with gradual decrease of temperature and in final steps, it is less likely to get worse solutions so the algorithm will move towards a good convergence solution (Fattahi, 2009).

    Proposed SA algorithm for this paper contains two inner and outer reaping loops. First the tasks are to be processed randomly on machine at first stage then, each task is to be allocated randomly to one of the machines at second stage. The inner loop was iterated by changing the second stage processor and making a neighborhood solution. Iterations start off the initial temperature and with gradual decrease and after reaching to environment temperature will stop. Then the outer loop will gain a neighborhood solution by changing the processors order and the inner loop will be iterated again.

    The algorithm has two inner and outer loops, the inner loop contains a homogeneous SA and the outer loop contains a heterogeneous SA. The outer loop is responsible for assigning the order of tasks to be processed on machine at first stage. The inner loop is responsible for allocating each task to one of the machines at second stage. First we assign an initial temperature for outer loop then we choose a random order for processing of task on machine at first stage. Next, we assign the inner loop initial temperature, while choosing a random order of processing for machines at second stage, we calculate the problem objective. Now according to SA algorithm, a neighborhood solution should be obtained by changing the allocated machine of each task. If the obtained solution is better than the previous one, it will be accepted otherwise we will obtain the solution by this formula: e Δ E T . If the solution is better than the produced random number, we will accept it. Then if the condition is balanced we reduce the temperature otherwise we repeat the loop until to reach the balance and also we repeat the inner loop as long as it reaches the environment temperature. The inner loop iteration will be continued to reach the environment temperature and the effort to find the solution will be also continued until the outer loop temperature reaches to environment temperature.

    3.3.The Proposed Heuristic Algorithm

    The proposed heuristic algorithm in this paper is derived into two algorithms: Shortest Process Time (SPT) and First Available Machine (FAM) algorithms. The objective of this proposed algorithm is to allocate each task among all available machines, to the machine with the least processing time and it contains the following steps:

    • 1. Arrange the tasks on machine of first stage in order of the shortest processing time.

    • 2. Allocate the first task to machine with the least processing time at second stage.

    • 3. Allocate the next task to machine with the earliest access time at second stage.

    • 4. If more than one machine is available, allocate the task to machine with the least processing time.

    • 5. Go back to the third step 3.

    3.4.Mathematical Model

    The Mathematical model is a two objective MILP model with minimizing F and T:

    M i n ( Z 1 , Z 2 ) Z 1 = 1 n j = 1 n F j Z 2 = 1 n j = 1 n T j

    Subject. to:

    I j i k = { 1 i f j o b j i s p r o c c e s s e d b y m a c h i n e i a t s t a g e k 0 i n o t h e r w i s e i = 1 m k I j i k = 1 j = 1 , , n ,    k = 1 , 2 O H j 1 , i k = 0 i = 1 , , m k ,    k = 1 , 2 , j = 1 O H j 1 , i k = q = 1 j 1 ( P q i k . I q i k ) j = 2 , , n F j = k = 1 2 i = 1 m k ( ( O H j 1 , i k + P j i k ) . I j i k ) j = 1 , , n d j = k = 1 2 ( 1 m k i = 1 m k P j i k ) + r o u n d ( U ( 0 , k = 1 2 i = 1 m k P j i k ) k = 1 2 m k )    j = 1 , , n T j = max ( 0 , F j d j )

    And parameters are used in MILP model are:

    • j counter of jobs

    • i of machines

    • k counter of stages

    • n number of jobs

    • mk number of machines at stage k

    • Pijk Process time of job j, on machine i, at stage k.

    • Fj Flow time of job j

    • Tj Tardiness of job j

    • dj Due date of job j

    • OHjik Access time of machine i, at stage k, for job j

    4.VALIDITY

    4.1.Setting the Proposed SA Parameters

    SA is a meta-heuristic searching algorithm that investigates the solution areas with producing neighborhood solutions. Simulated annealing has been successfully applied to various difficult combinatorial optimization problems. SA can be viewed as a process which, given a neighborhood structure, attempts to move from the current solution to one of its neighbors. Starting from an initial solution, SA generates a new solution in the neighborhood of the current solution. It’s undeniable that increasing the number of iterations is compatible with increasing the time of solving the problem, therefore the SA parameters should be obtained precisely. in order to not defining the fixed first temperature, for all problems of under study, the initial temperatures of outer and inner loops are defined as a part of number of tasks in each problem. So the maximum possible iterations in outer loop will be obtained by n! and the maximum possible iterations in inner loop will be obtained by 2n. Since the maximum possible iterations of outer loop are more than the maximum possible iterations of inner loop, the initial temperature of outer loop is considered more than the initial temperature of inner loop. In this study the initial temperature of outer loop will be obtained by 2ln(n) ×1,000 and the initial temperature of inner loop will be also ob- tained by 2log(n) ×1,000. then the temperature is reduced in each iteration geometrically. The iteration in outer and inner loops will be continued as long as it reaches to environment temperature. The environmental temperature for both inner and outer loops is 25 degree of centigrade. The static balance condition in inner loop is defined as 10 iterations in each inner loop temperature. In this step, we have studied 3 initial temperatures which are assigned according to the number of tasks for each outer and inner loop; they are shown in Table 1. It is obvious that the more the initial temperature of SA is, the more the number of iterations and time of solving problem will be. The result of study over 100 random problems containing 20 tasks indicates that high number of iterations on temperature of 1,000×n for both loops won’t have any great influence on the optimal solution and only increases the time of solving problem intensively. If the initial temperature is obtained by 100× n , the proper solutions won’t be obtained for problems with fewer tasks; hence, the initial temperature of outer loop has been defined according to 2ln(n) ×1,000 and the initial temperature of inner loop has been defined according to 2log(n) ×1,000 because in these temperatures the number of iterations of outer and inner loops and also as a result the time of solving problem will be reduced and for many problems under study, the most appropriate solutions will be obtained too.

    In the following steps in order to assign the proper percentage of lowering temperature in each iteration in SA algorithm, some defined problems with the percentages of 98%, 95% and 90% are solved for both loops then considering the compatibility of problem solving time and quality of obtained solutions, the percentage of lowering temperature has been considered 95% for inner loop and also the percentage of lowering temperature has been considered 90% for outer loop.

    For static balance of 10 iterations in each inner loop temperature, we considered 100 random problems containing 20 produced tasks. The obtained solutions with iterations of 5, 10 and 20 in inner loop were studied; the result indicated that in more than 87% of problems, the solutions obtained from 10 iterations were the same as the solutions obtained from 20 iterations while the problem solving time has increased to almost 160% and it is 2.6 times more.

    4.2.Results

    In this study two criteria of minimizing the average tardiness (T) and minimizing the average flow time (F) are considered. 500 randomly produced problems are solved by the heuristic algorithm and the SA algorithm and their results are compared. The processing time on machine at first stage is assigned randomly between 10- 20 hours and also the processing time on machines at second stage is assigned randomly between 20-40 hours. The due dates is also defined according to Jolai et al. (2013) formula:

    d d j = P 1 j + min  P 2 j + r o u n d ( U ( 0 , j = 1 n ( P 1 j + min P 2 j ) ) m 1 + m 2 )

    in Table 2, number of random problems is shown in first column, number of tasks with random times in each problem is shown in second column, the third column shows the number of problems that had reached better solutions by heuristic method or had the same solution as SA algorithm, the forth column shows the improved percentage of solutions obtained by heuristic method in comparison to solutions obtained by SA algorithm in 100 problems of under study with as many tasks as possible. Column 5th shows the ratio of problem solving time for 100 random problems by using SA algorithm to the time for same random problems by using heuristic method. As it is shown in above table, the heuristic method in average 90.4% problems has lead to better solutions or at least the solutions are the same as those based on SA algorithm. The total number of solutions obtained of 500 problems in heuristic method is 15.04% better than the average solutions obtained according to SA algorithm. And also in heuristic method, the solutions will be obtained 58 times as fast as SA algorithm method.

    5.CONCLUSION

    The heuristic SAW method is better than two other algorithms and the optimal solution of this method is 15.04% better than the average solution in other three methods. The time of problem solving in heuristic method is less than the time in SA algorithm. The important point to mention is that the heuristic method in both criteria is not necessarily better than other methods, but in both criteria and according to SAW method, it has better results. Although heuristic method in solving problems with more number of tasks is much better than those in methods based on SA algorithm, the rate of better solutions even in problems with 10 tasks is 14% more than methods based on SA algorithm.

    Figure

    IEMS-16-265_F1.gif

    A hybrid flow shop problem.

    IEMS-16-265_F2.gif

    Two solutions with Min Fand Min T .

    Table

    Initial temperature of inner and outer loops based on the SA algorithm

    Comparing heuristic method and two methods based on SA algorithm in two-criteria

    REFERENCES

    1. Choong F , Phon-Amnuaisuk S , Alias M Y (2011) Metaheuristic methods in hybrid flow-shop scheduling problem , Expert Systems with Applications, Vol.38 (9) ; pp.10787-10793
    2. Fattahi P (2009) Metaheuristic Algorithms, Bu-Ali Sina University Press,
    3. Gholami S , Moosaloo V (2011) Hybrid flow shop scheduling problem with unrelated parallel machines, setup times dependent on scheduling and central warehouses capacity constraints , Eighth International Conference on Industrial Engineering, Amirkabir University of Technology,
    4. Ghomi S M T F , Zandieh M (2002) A framework and classification of manufacturing system modeling , Second National Conference on Industrial Engineering, University of Yazd,
    5. Gupta J N D (1988) Two-stage hybrid flow shop scheduling problem , Journal of the Operational Research Society, Vol.39 (4) ; pp.359-364
    6. Jolai F , Asefi H , Rabiee M , Ramezanian P (2013) Bi-objective simulated annealing approaches for nowait two-stage flexible flow shop problem , Sharif University of Technology, Vol.20 (3) ; pp.861-872
    7. Kumar P , Sanjoy A , Abdullahil A (2010) Minimization of work-in-process inventory in hybrid flowshop scheduling using fuzzy logic , International Journal of Industrial Engineering: Theory Applications and Practice, Vol.17 (2) ; pp.115-127
    8. Linn R , Zhang W (1999) Hybrid flow shop scheduling: A survey , Computers & Industrial Engineering, Vol.37 (1-2) ; pp.57-61
    9. Momenzadeh S B (2012) Performance of Circular Opening in Beam Web Connections , Life ScienceJournal, Vol.9 (3) ; pp.1377-1383
    10. Momenzadeh S , Seker O , Shen J (2017) Observed Seismic Demand on Columns in SCBFs,
    11. Morais M F , Filho M G , Boiko T J P (2013) Hybrid flow shop scheduling problems involving setup considerations: A literature review and analysis , International Journal of Industrial Engineering: Theory, Applications and Practice, Vol.20 (11-12)
    12. Rezaeian J , Mahdavi I , Nekzad F (2013) Schedulin a few pieces products at a two-stage hybrid assembly flow shop system , The Tenth International Conference on Industrial Engineering, Tehran University,
    13. Ribas I , Leisten R , Framinan J M (2010) Review and classification of hybrid flowshop scheduling problems from a production system and a solutions procedure perspective , Computers & Operations Research, Vol.37 (8) ; pp.1439-1454
    14. Ruiz R , Vázquez-Rodríguez J A (2010) The hybrid flow shop scheduling problem , European Journal of Operational Research, Vol.205 (1) ; pp.1-18
    15. Shen J , Seker O , Akbas B , Seker P , Momenzadeh S , Faytarouni M (2017) Seismic performance of concentrically braced frames with and without brace buckling , Engineering Structures, Vol.141 ; pp.461-481
    16. Taghaddosi S , Khoshalhan F (2010) A review of the literature and research on multi-objective flow shop scheduling , International Journal of Industrial Engineering & Production Management, Vol.3 (21) ; pp.14-22
    17. Wang S J , Liu M (2013) A heuristic method for two-stage hybrid flowshop with dedicated machines , Computers & Operations Research, Vol.40 (1) ; pp.438-450
    18. Yang J H (2015) Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage , Computers & OperationsResearch, Vol.58 ; pp.1-8