Integrating sequence dependent group scheduling problem
and preventive maintenance in flexible flow shops
Alireza Khamseha , Fariborz Jolaia, Morteza Babaeic
aDepartment of Industrial Engineering, University of Tehran, Tehran, Iran
bDepartment of Electrical and Computer Engineering, AzadUniversity, Qazvin, Iran
Abstract
A widespread assumption in scheduling problems is that machines are continuously available, whereas machines can be unavailable due to different reasons such as breakdown or preventive maintenance. This study addresses sequence dependent group scheduling problem with preventive maintenance activities in flexible flow shops in order to minimize makespan. In a group scheduling problem, scheduling of groups and jobs within each group is determined. As the considered problem is strongly NP-hard two meta-heuristics based on simulated annealing (SA) and genetic algorithm (GA)are used to solve it. A local search procedure is put into operation to enhance the quality of solution in SA-based algorithm. In addition, matrix solution representation is a key feature of GA-based algorithm. In order to set parameters and achieving better performance of the algorithms, we exploit Taguchi robust parameter design method. The performance of the proposed algorithms is evaluated on a variety of test problems. To comparing algorithms makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of the algorithms. Generally results indicate that GA-based algorithm has better performance and outperforms SA-based algorithm.
Keywords: Group scheduling, Preventive maintenance, Sequence dependent setup times, Simulated annealing, Genetic algorithm, Flexible flow shop, Taguchi robust parameter design.
1) Introduction
Depending on the number of operations required to process a job and on the number of available machines per operation, manufacturing systems have a variety of different flow patterns. One of the most common flow patterns which is spreading increasingly and countered in industries such as automobile, tile, printed circuit board, and textile is flexible flow shop. In this context, facilities arranged in a linear fashion and jobs proceeded in different stages, so that the flow of products is unidirectional. At least one stage must have multiple machines and these parallel machines could be identical, uniform, or unrelated. Jobs have not to go through all stages and permitted to skip certain stages [1].
Cellular manufacturing (CM) can be defined as an application of group technology. The concept of group technology is based on the simplification and standardization process, which appeared at the beginning of 20th century. Implementing CM can result in many benefits such as reduction in setup times and work in-process inventory as well as improvement in machine utilization and employee moral [2]. In order to exploit CM, three steps must be done before actual production. First, part families and manufacturing cells need to be determined. Second, part families assign to manufacturing cells. Finally, part families must be scheduled in manufacturing cells [3].Assigning twoor more groups to a cell results in a problem known as group scheduling. Thus, group scheduling consists of two levels, namely scheduling of parts belonging to each group and scheduling of groups themselves is determined at levels 1 and 2 respectively.
Another important subject exists in industries is setup. Setup includes work to prepare the machine, process, or shop for the purpose of production. Setup time is a significant factor for production scheduling in all flow patterns and it may easily consume more than 20% of available machine capacity if not well handled [4]. In addition, the completion time of the production and machine setups are influenced by production mix and production sequence. Generally there are two types of setup: sequence independent and sequence dependent. In the former, setup depends only on the job to be processed whereas sequence dependent setup depends on both the job to be processed and the immediately preceding job.
Machines could be unavailable because of various causes in scheduling horizon. One of these reasons is preventive maintenance that is closely related to production scheduling. Maintenance understood as the operations or techniques that allow tomaintain or restore equipment to a specific state and guarantee a given service. In order to achieve an optimum scheduling it is unavoidable to consider scheduling and maintenance operations simultaneously. Three are different preventive maintenance policies implied in real industries to reduce breakdown rate [31].
In this paper we attempt to integrate production scheduling problem with preventive maintenance activities to minimize completion time of the scheduling called makespan. The motivation of studying the problem with mentioned context comes from the need for research on real-world scheduling problems and production practice. Since there are a lot of variety of scheduling problems with the mentioned characteristics, to better definition of the problem, following assumptions is considered:
all data are known deterministically
no preemption is allowed
there are infinite buffers between stages
there is no travel time between stages
all jobs are available at the beginning of scheduling horizon
parallel machines are identical
In order to figure out the mentioned practical problem, two solution algorithms based on SA and GA are developed in this study. To promote the effectiveness of SA-based algorithm it is hybridized with a local search procedure. Since one of the most important factors that influences the performance of GA-based algorithm is solution representation, a new idea for representing the solution based on matrix structure is proposed in this paper.
The rest of the paper is organized as follows: in the following section we provide a literature review of the problem. In the section 3, some aspects of PM are briefly discussed. Proposed solution algorithms based on simulated annealing and genetic algorithm in order to solve the problem are explained in section 4. The waysof data generation and parameter adjusting are described in section 5. For adjusting parameters, we exploit Taguchi robust parameter design. The result of implementing proposed meta-heuristics is discussed in section 7. The last section concludes the paper with a look at future works.
2) Literature Review
This literature review will have one component regarding flexible flow shop and group scheduling and a second regarding integrating production scheduling and preventive maintenance.
2-1) Literature review of flexible flow shop and group scheduling
The flow shop problem was first studied by Jahnson [1] for two machines with the objective of minimizing makespan. After this a lot of different extensions were examined by numerous authors. Sule [2] and Proust et al. [3] considered the two-machine flow shop scheduling problem with sequence independent setup and removal time separated. Gupta and Darrow [4,5] recognized that even sequence dependent two machine problem with minimizing makespan is NP-hard. Kruz and Askin [6,7] examined scheduling rules foe sequence dependent setups in flexible flow lines. A complete survey of scheduling problems with setup time or costs is provided by Allahvedi et al. [8]. Minimizing makespan in a two-machine sequence independent setup group scheduling problem addressed by Logendran and Sriskandarejah [9].
A polynomial-time algorithm proposed by Ham et al. [10] to minimize makespan in a sequence dependent two-machine group scheduling problem. Schaller [11] developed lower bounds for sequence dependent flow shop group scheduling. The sequence dependent group scheduling with some dynamic conditions examined by Reddy and Nerendran [12]. Logendran et al. [13] considered group scheduling in flexible flow shop with sequence independent setup times. Then, this problem with sequence dependent setups addressed by Logendran et al. [14]. They proposed three tabu search based algorithms to minimize makespan. Zandieh et al. [15] examined the same problem and developed two SA and GA based algorithms that outperformed the TS based algorithms proposed by Lodendran et al. [14].
2-2) Literature review of integrating production scheduling and preventive maintenance
Compared to the different variant of flow shop problem, problems under availability constraint are not widely studied. However, there is a rapid increase in integrating production scheduling and preventive maintenance. One reason could be make them more practical and efficient. Lee [16] studied the problem of minimizing the makespan in a two-machine flow shop with an availability constraint. He proved that the problem with one preventive period on only one machine constraint, where the machine is unavailable in an internal is NP-hard. Yang et al. [17] considered a two-machine flow shop scheduling problem where it needs a constraint time to maintain the machine.
Minimizing the total weighted completion time of jobs on a single machine with only one maintenance activity studied by Graves and Lee [18]. Chen[19]addressed a single machine scheduling problem with periodic maintenance where jobs are nonresumable. Single machine scheduling problem with availability constraint considered in some other studies [20,21,22,23]. Schmidt [24] reviewed the results related to deterministic scheduling problems where machines are not continuously available for processing.
Two machines scheduling problem with preventive maintenance investigated in Chen [25], Kubiak et al.[26], Blazewicz et al. [27], and Allaoui and Artiba [28].
Makespan minimization in the flow shop scheduling problem with availability constraints studied by Aggoune [29]. He considered two variants where in the first, starting times of maintenance tasks are fixed while in the second one maintenance tasks must be performed on a given time window.
Scheduling preemptive jobs in a two-machine flow shop with availability constraint on the first machine considered by Berit [30]. Perhaps the work by Ruiz et al. [31] is the best one that can be addressed for integrating production scheduling and preventive maintenance activities in a flexible flow shop. They considered different preventive maintenance policies on machines and developed some heuristics in order to minimize makespan.
To the authors best knowledge there is no work trying to integrate group scheduling problem and preventive maintenance activities in flexible flow shop. Because of the importance of this problem in the real-world conditions, we decided to work on this problem.
3) Preventive maintenance
Preventive maintenance is an interval-based surveillance method in which periodic inspection are performed on equipment to determine the progress of wear in its components and subsystems. When wear has advanced to a degree that warrants correction, maintenance is performed on the equipment. Periodically, a preventive maintenance inspection is made. If the inspection reveals serious wear, some maintenance operation is performed to restore the component or subassembly to a good state of repair, and reduce the probability of failure. A PM system increase the probability that the equipment will performed as expected without failure until the next inspection due date.
Maintenance can be defined as a set of predefined activities that caused to maintain or restore the equipment in operational state. Generally, there are two major kind of maintenance: corrective maintenance (CM) and preventive maintenance (PM). Reliability, maintenance and maintainability are important in nearly every endeavor that deals with engineered and manufactured goods. Preventive maintenance actions generally require shutdown of an operational system and are intended to increase the length of its lifetime and/or its reliability. When a PM activity is done on machines and equipment, they are still operating and failure or breakdown have not take place. On the other hand CM comprises actions taken to restore a failed product or system to an operational state. There are different PM policies available in literature on reliability. One of these policies is finding an optimal period for preventive maintenance based on maximizing the equipment's availability that is described as follows [31].
Let X be a non-negative random variable representing the lifetimeof the machine. Suppose this random variable is governed by a Weibull probability distribution: X~W[η,β], where η and β are scale and shape parameters and β>1.
Survival function, also known as the reliability function, gives the probability of surviving beyond time t is defined as t>0 (1)
The hazard function or the hazard rate is defined by
(2)
and expresses the probability to fail in the next small interval of time, given survival to time t. this function for Weibull random variable is defined as
t>0 (3)
Limiting availability is defined according to
(4)
where MTTF is the mean time to failure and about Weibull probability distribution can be calculated by
(5)
that Г(•) shows the value of Gamma function and MTTR is the mean time to repair.
When a machine fails, minimal repairs are performed to restore the machine back to its operating condition without altering its effective age. Since PM restores the machine to a "good as new" condition, machine performance can be modeled using a renewal process, where the renewal points correspond to the completion of a PM activity. Because it is assumed that the repair is minimal, the number of failures during each cycle of the renewal process occurs according to a non-homogeneous Poisson process.
As mentioned one criterion to determine the interval between two consecutive PM activities is based on maximizing the system's availability. With the above explanations optimum PM interval (TPM) can be calculated by following expression, where tp is the length of PM activity and tr is the length of the machine repair's time.
(6)
4) Proposed meta-heuristics
Since the flexible flow shop scheduling problem with preventive maintenance is strongly NP-hard, algorithms for finding an optimal solution in polynomial time are unlikely to exist. Thus, in this section we introduce two meta-heuristic methods to find near optimal solutions.
4-1) Simulated annealing
Simulated annealing (SA) was introduced by Metropolis et al. [32] and popularized by Kirkpatrick et al. [33]. Simulated annealing is motivated by an analogy to annealing in solids. It is an enhanced version of local optimization in which an initial solution is repeatedly improved by making small local alterations. SA not only accepts changes that improve objective function but also some changes that do not improve it in order to avoid being trapped in a poor local optimum. A SA-based algorithm starts from an initial solution S. using neighborhood solution generator a new solution S' generated. The changes in objective function value δ = f(S) – f(S'), is calculated. If δ<0, then current solution is replaced by new solution. On the other hand (when δ≥0), new solution is accepted according to a probabilistic criterion as where T is control parameter called temperature.
The final performance of the SA is influenced by various parameters and factors such as: initial solution, type of cooling schedule, initial temperature, number of temperature decline, number of iterations at each temperature, and neighborhood generation mechanism.
4-1-1) Initial solution
In order to begin the search as well as investigate the influence of starting point on the algorithm, two kinds of initial solutions are considered. In the first one sequence of groups and jobs within each group is produced in a random manner and in the second one this sequence gained by following numerical ordering.
4-1-2) Cooling schedule model
Cooling schedule determines the pattern of temperature decline between initial and final temperature, and affects the probability of accepting a worse solution. We think about three types of cooling schedule, namely linear, exponential, and hyperbolic. These patterns can be formulated as follows [34]:
Linear pattern:
Exponential pattern: ; ;
Hyperbolic pattern:
T0, Tf, Tiand N represent initial temperature, final temperature, temperature at iteration i, and number of temperatures between T0 and Tf. In all above cases i can vary from 1 to N. Also a graphical view of these patterns is provided in Fig.1.
4-1-3) Neighborhood generation mechanism (NGM)
One of the most significant factors that can influence the quality of SA is how to move from current solution to another. There are different NGMs in literature and in this research we study three NGMs (referred to as NGM1, NGM2, and NGM3) to examine how they affect the performance of SA and enhance the quality of solutions.
In NGM1, one group and one job belonging to it are randomly picked and new positions for them determined by chance. NGM2 first swaps the positions of two randomly selected groups and the same action is taken for two jobs within each two selected groups. Finally, in NGM3 a cutting point between one and number of groups mines one is generated and positions of the sets of groups on the right and left hand of this point are changed. Then position of one randomly selected job in each group belonging the smaller set is established again. The levels of other important factors and further explanations are discussed in section 5.
4-1-4) Local search
For the purpose of ameliorating solution quality and concentrating the search, a local search is utilized in the search process as follows: before updating temperature, current solution examined by exchanging the first job in the first group of the sequence with the next job in the same group. If this improves the makespan the action is continued by subsequent job otherwise the process is stopped. After finishing jobs belonging to the first group it keeps up with the next group in the sequence. At each step the current best solution will be replaced with the new solution, if new solution is better.
4-2) Genetic algorithm
Genetic algorithm (GA) that is motivated by Darwin's theory of evolution of different species, was introduced by Holland and his colleagues in the 1960s and 1970s [35]. GA is a population-based approach that in which each solution represented by a chromosome comprising some genes. During solving process a set of chromosomes called population are evoluted and progressed toward solutions with higher desirability. This evolution is fulfilled via generating a new generation by genetic operators namely, crossover, reproduction, and mutation. The efficiency of GA greatly depends on the correct choice of solution representation, selection mechanism, stopping criteria, genetic operators, and parameter values.
In this study, the idea of random key genetic algorithm (RKGA) is put to use for representing solutions. At stage one, each solution is represented by a matrix, where n_g and q expressing number of groups and maximum number of jobs within groups respectively. The first column of this matrix states the assignment of groups to stage one's machines which integer part indicates machine number and fraction part shows the sequence. In order to determine the job sequence within groups, real numbers in the interval of zero and one are used that the job with smaller number is located first in the sequence. Fig. 2 illustrates an example of solution representation. In this example we assume there are three groups and each has three jobs within. Additionally two parallel machines exist at stage one.