Nội dung

International Journal of Industrial Engineering Computations 8 (2017) 399–426 Contents lists available at GrowingScience International Journal of Industrial Engineering Computations homepage: www.GrowingScience.com/ijiec Flow-shop scheduling problem under uncertainties: Review and trends Eliana María González-Neiraa,b*, Jairo R. Montoya-Torresc and David Barrerab aDoctorado en Logística y Gestión de Cadenas de Suministros, Universidad de La Sabana, Km 7 autopista norte de Bogotá, D.C., Chía, Colombia bDepartamento de Ingeniería Industrial, Facultad de Ingeniería, Pontificia Universidad Javeriana, Cra. 7 No. 40-62 - Edificio José Gabriel Maldonado, Bogotá D.C., Colombia cSchool of Management, Universidad de los Andes, Calle 21 # 1-20, Bogotá, D.C., Colombia CHRONICLE ABSTRACT Article history: Received January 2 2017 Received in Revised Format January 3 2017 Accepted February 7 2017 Available online February 8 2017 Keywords: Flow shop Flexible flow shop Uncertainties Stochastic Fuzzy Production logistics Review Among the different tasks in production logistics, job scheduling is one of the most important at the operational decision-making level to enable organizations to achieve competiveness. Scheduling consists in the allocation of limited resources to activities over time in order to achieve one or more optimization objectives. Flow-shop (FS) scheduling problems encompass the sequencing processes in environments in which the activities or operations are performed in a serial flow. This type of configuration includes assembly lines and the chemical, electronic, food, and metallurgical industries, among others. Scheduling has been mostly investigated for the deterministic cases, in which all parameters are known in advance and do not vary over time. Nevertheless, in real-world situations, events are frequently subject to uncertainties that can affect the decision-making process. Thus, it is important to study scheduling and sequencing activities under uncertainties since they can cause infeasibilities and disturbances. The purpose of this paper is to provide a general overview of the FS scheduling problem under uncertainties and its role in production logistics and to draw up opportunities for further research. To this end, 100 papers about FS and flexible flow-shop scheduling problems published from 2001 to October 2016 were analyzed and classified. Trends in the reviewed literature are presented and finally some research opportunities in the field are proposed. © 2017 Growing Science Ltd. All rights reserved 1. Introduction Logistics and supply chain concepts have evolved over the years, initially involving only transportation activities and then expanding to include product flows, information flows, and reverse flows until finally reverse flows, integrated chains, and networks were incorporated. Although there is diversity in definitions, there is a common understanding that logistics involves three principal stages called supply, production, and distribution (Farahani et al., 2014). Despite this taxonomy, many distribution and production problems share similar mathematical formulations and solution procedures. Due to the vast variety of problems and knowledge that all these stages comprise, we are going to focus on production * Corresponding author Tel: +57-1-3208320 Ext. 5306. E-mail: eliana.gonzalez@javeriana.edu.co (E. M. González-Neira) © 2017 Growing Science Ltd. All rights reserved. doi: 10.5267/j.ijiec.2017.2.001 400 logistics processes, with a particular view on scheduling of jobs and tasks. Indeed, many product distribution problems have been analyzed in the literature as transportation problems, but they can also be viewed as scheduling problems. So, scheduling activities are performed in at least two stages of the logistics system. Generally speaking, scheduling consists in the allocation of limited resources to activities over time in order to optimize one or more desired objectives established by decision-makers. Both resources and activities can be of different types, so the theory of scheduling has many applications in manufacturing and services, playing a crucial role in the competitiveness of organizations and industries (Brucker, 2007; Leung et al., 2004; Pinedo, 2012). Scheduling problems can be classified depending on the configuration of resources (often called the production environment). Among the principal configurations, singlemachine, parallel-machines, flow-shop (FS), flexible flow-shop (FFS), job-shop, flexible job-shop, and open-shop configurations can be found and can be analyzed in a deterministic or a stochastic way (Pinedo, 2012). Particularly, FS problems (including FFS) have been extensively studied due to their versatility and applicability in the textile, chemical, electronics, automobile manufacturing (Mirsanei et al., 2010; Zandieh et al., 2006), iron and steel (Pan et al., 2013), food processing, ceramic tile (Ruiz et al., 2008), packaging (Adler et al., 1993), pharmaceutical, and paper (Gholami et al., 2009) industries, among others. The standard FS problem consists in machines (resources) in series. There are jobs (tasks) that have to be processed on every machine. All jobs must follow the same processing route on the shop floor; that is, jobs are performed initially on the first machine, next on the second machine, and so on, until machine m is reached. The decision to be taken is to determine the processing sequence of the n jobs on each machine. This results in a solution space of ! (Pinedo, 2012). When the objective function is the makespan, the problem has been proved to be strongly NP-complete for three or more machines (Lee, Cheng, & Lin, 1993) and for the tardiness objective (Du et al., 2012). A generalization of the FS and parallel-machines environments is the FFS. In this case there are stages, and at least one stage has two or more machines in parallel that process the same kind of operation. Thus, the decision to be made is which of the parallel machines each job should be allocated to at each stage. It can be seen that when there is only one machine in all stages then the problem is a standard FS one (Pinedo, 2012). Most of the studies in FS and FFS scheduling have considered that all information is known, that is, deterministic. Nevertheless, within organizations, various parameters are not exactly known and vary over time, causing deterministic decisions to be inadequate. That is why scheduling under uncertainties is a very important issue that has received more attention from researchers in the last years (Elyasi & Salmasi, 2013a; Juan et al., 2014). Particularly in the area of stochastic flow shop (SFS), only one literature review has been published, in the year 2000 by (Gourgand et al., 2000a). Nevertheless, considering the growing and significance of this field it is important to update the state of the art and give some future directions for research. This paper provides a general view of the developments in FS and FFS scheduling under uncertainties over the last 15 years and how these advances influence the research on production logistics. Section 2 describes the notation used for the literature review. Section 3 describes the different solution approaches presented in the literature and current state of research. Finally, several directions for future research are outlined in Section 4. 2. Notation In order to present the literature review on FS and FFS problems under uncertainties we are going to follow the notation originally presented by Graham et al. (1979) and later adapted by Gourgand et al. (2000b) for stochastic static FS problems. In order to include (FFS) problems, we extend the notation presented by Gourgand et al. (2000b) since it was designed to classify stochastic FS problems only. We also adapted the notation to include unknown parameters modeled using both stochastic distribution and E. M. González-Neira et al. / International Journal of Industrial Engineering Computations 8 (2017) 401 fuzzy sets. According to the notation in Graham et al. (1979), scheduling problems can be represented using three fields named | | . The field indicates the shop configurations. For the purpose of this review, two symbols are required: (an FS with machines) and (an FFS with stages). Field denotes the special constraints and assumptions which differ from the standard problem of the specific shop. It includes uncertain parameters and the way in which they are modeled. Table 1 presents the basic notation of parameters (in the deterministic version) and characteristics of the shop problem. Depending on how the uncertain parameters are modeled, let us use the following conventions:      When a parameter is modeled using a probability distribution we will denote it as ~ , where is the probability function. For example, if the processing times of in an FS problem are modeled with a normal distribution with mean job on machine and variance , then its notation is ~ , . When a general distribution is used, the parameter is denoted as ~ If the uncertain parameter is modeled as a fuzzy number, the notation becomes . , that is, If the parameter is not modeled with a distribution probability or as a fuzzy number but it can take random values in a specific interval, it is denoted as . For example, if the due date of job varies between the values and . For inverse scheduling in which a controllable parameter is adjusted, we denote it as . Table 1 Notation used in Type Parameters field Notation Special characteristics , Meaning Due date of job Processing time of job on machine (in an FS) or processing time of job in stage (in an FFS) Release date of job When a machine switches over from one job family to another, denotes the sequence-dependent setup times between family and job family Sequence-independent setup time of job on machine Sequence-dependent setup time when job is going to be processed just after job on machine Transportation time between machines and in an FS or between stages and in an FFS Weights of jobs Unrelated parallel machines in the case of FFS environments Breakdown level of the shop. Some researches uses this approach to define the time between failures (TBF) (Holthaus, 1999) Time taken for basic preventive maintenance Time taken for minimal preventive maintenance Size of job j. This characteristic can be used when a machine can process batches and jobs have different sizes Machines can process a batch of jobs simultaneously When the buffer capacities between machines in an FS or between stages in an FFS are limited, the jobs must wait in the previous machine (FS) or stage (FFS), blocking it until sufficient space is released in the buffer. Machine breakdowns. The information enclosed in parentheses is: the time between failures and the time to repair . Degradation of machines due to shocks. It means that machines have to be subject to preventive maintenance Dynamic arrivals. Families of jobs. When jobs of the same family or group are processed consecutively on the same machine, a setup time for each job is not needed. Lot sizing Lot streaming No wait. Jobs are not allowed to wait between machines Precedence. It can take place in parallel machines of a FFS, implying that a job can only be processed after all predecessors have been completed. Preemption. The processing of a job on a machine can be interrupted and finished later. Penalties may apply. Permutation. This only happens in FS and indicates that the execution sequence of jobs in all machines is the same. Recirculation or reentrant: a job may visit a machine or a stage more than once. Order splitting Finally, field corresponds to the decision criteria or optimization objectives. In order to explain the possible objectives in the field, let us define: 402        , the completion time of job on machine for FS or in stage for an FFS problem , the completion time of job j on the last machine in an FS or in the last stage in an FFS , the flow time of job , calculated as , the lateness of job , calculated as , the tardiness of job , calculated as max ,0 , the earliness of job , calculated as max ,0 1 if the job is tardy, that is, if 0, and 0 otherwise. The possible objective functions for the deterministic counterparts of scheduling problems are presented in Table 2. It is important to note that the field is extended to express one of the following ways to deal with uncertainty: 1 . . Table 2 Objective functions in deterministic scheduling max Formula Meaning Makespan or maximum completion time max Maximum flow time Notation max Maximum lateness max Maximum tardiness Total/average completion time Total/average weighted completion time Total/average flow time Total/average weighted flow time Total tardiness Total weighted tardiness Total earliness Total weighted earliness Total number of tardy jobs Work-in-process inventory Throughput time The complete | | notation presented is illustrated using five examples:  corresponds to an FS environment with three machines in which the 3 processing times are modeled using fuzzy numbers and the objective function is the makespan. E. M. González-Neira et al. / International Journal of Industrial Engineering Computations 8 (2017)     403 ̅, | is an FFS with stages in which the processing times ~ , follow a lognormal distribution with mean and standard deviation . The problem analyzes a bi-objective function that is solved through a Pareto approach. For this case, the objectives are the expected total completion time and the expected total tardiness. , , ~ ∙ ∙ is an FFS with stages in which machine breakdowns are stochastic. The time between failures follows an exponential distribution with mean at each stage. The time to repair follows a lognormal distribution with mean and standard deviation of at stage . The objective function is the minimization of the flow time with probability 1. consists of an FS with machines that considers deterministic release times. The objective function is to minimize the weighted sum of makespan and tardiness, but the weights for each function and are not known and are thus modeled as fuzzy numbers. corresponds to an FS environment with machines in which the due dates are random variables that can vary in an interval. The objective is to construct a robust schedule according to a maximum tardiness criterion. 3. Literature review As mentioned previously, FS and FFS under uncertainties have not been well studied as deterministic counterparts. Only one literature review presented by (Gourgand et al., 2000a) was found for the static version of the stochastic FS. Those authors noticed that the majority of researches considered that either processing times or breakdowns of machines were subject to uncertainties. In addition, that review revealed that the majority of the revised works analyzed the cases of FS with only two machines. Since then, this field has been growing and there are more complex applications nowadays. The nomenclature presented in the previous section was used to summarize the type of problem addressed in 100 papers published between 2001 and October 2016. The year 2001 was chosen as the starting point in time as it corresponds to the time immediately after the publication of the review in (Gourgand et al., 2000a). According to Fink (1998) and Badger et al. (2000), from a methodological point of view, a literature review is a systematic, explicit, and reproducible approach for identifying, evaluating, and interpreting the existing body of documents. This paper follows the principles of systematic literature reviews, in contrast to narrative reviews, by being more explicit in the selection of the studies and employing rigorous and reproducible evaluation methods (Delbufalo, 2012; Thomé et al., 2016). A set of criteria was defined to collect and identify the research papers from the Science Citation Index compiled by Clarivate Analytics (formerly the Institute for Scientific Information, ISI) and SCOPUS databases. The inclusion and exclusion criteria are explained next:   Inclusion criteria: Title–abstract–keywords (flowshop OR "flow shop" OR flowline) AND (random OR randomness OR stochastic OR uncertainty OR uncertainties OR robust OR robustness OR fuzzy) AND publication year > 2000 Exclusion criteria: o Random elements are part of the solution method but not characteristics of the parameters. For example, all parameters and objective function are deterministic but the solution method is a random key genetic algorithm. o The article is not about scheduling. For example, the main topic of the paper is “subsea flowline buckle capacity considering uncertainty”. o The paper is written in a language other than English. o The paper was published in conference proceedings. The list of reviewed papers is presented in Table 3. The first column of the table indicates the bibliographical reference (including the publication year), the second one describes the problem 404 addressed in the paper with the proposed notation, and the third column briefly describes the type of solution approach and in some cases other details that may be of interest. This table follows a similar format to that presented in (Ruiz & Vázquez-Rodríguez, 2010). The fourth to sixth columns indicate which approach was used for modeling uncertain parameters. The seventh to eleventh columns indicate what kind of solution method was used to deal with uncertainty. Lastly, the twelfth to fourteenth columns show what kind of method was employed for optimization. As illustrated in the table, there is a trend of an increase in the number of papers published on FS and FFS under uncertainties. This is helped by the existence of more rapid computers and advances that allow more complex problems to be solved. Fig. 1 shows the evolution of the number of papers separately for FS and FFS under uncertainties and the total values. There is a big difference between FS and FFS, with FFS representing 25% of the revised works. 14 12 10 8 6 4 2 0 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 FFS FS Total Fig. 1. Number of papers per year on FS and FFS under uncertainties There are some issues to be highlighted from the literature, so the following subsections summarize the findings in terms of four characteristics:     Uncertain parameters and methods to describe them (fuzzy, bounded, probability) Approach used to deal with uncertainty (fuzzy, robust, stochastic (not simulation), simulationoptimization and interval theory) Optimization methods Objective function (Temİz & Erol, 2004) 2 (Kalczynski & Kamburowski, 2004) (Sotskov et al., 2004) 2 3 3| 3 2 2 ~ ~ Problem (Allahverdi, 2004) (Balasubramanian & Grossmann, 2003) (Celano et al. , 2003) (Chutima & Yiangkamolsing, 2003) (Gourgand et al., 2003) (Balasubramanian & Grossmann, 2002) (Allahverdi et al., 2003) (Alcaide et al., 2002) (Allahverdi & Savsar, 2001) Reference , , ~ , , ~ , , , ̅ ̅ ̅ , , , , . . , | Bounded Fuzzy branch and bound √ √ √ Genetic algorithm Fuzzy genetic algorithm Markov optimization and simulationoptimization with simulated annealing. The Markov chain approach presents lower computational times in small instances, while the simulation approach is recommended for larger instances with makespan minimization. Dominance analysis. Optimal solutions are obtained when certain conditions are satisfied. New scheduling rule that generalizes Johnson’s and Talwar’s rules Dominance analysis √ Fuzzy set theory with tabu search √ √ √ √ √ √ Dominance analysis Fuzzy √ √ √ Probability Dynamic algorithm to convert a problem subject to breakdowns into a problem without breakdowns Branch and bound Dominance analysis Solution approach Modeling of uncertain parameters Fuzzy √ √ √ √ Stochastic (not simulation) √ √ √ √ √ √ Simulation-optimization Robust Approach taken to deal with uncertainty Interval theory √ √ √ Optimization method √ √ √ √ √ √ √ Exact E. M. González-Neira et al. / International Journal of Industrial Engineering Computations 8 (2017) √ √ Heuristic Table 3 Classification of the reviewed works √ √ √ √ Metaheuristic 405 (Pawel Jan Kalczynski & Kamburowski, 2006) (Petrovic & Song, 2006) 2 2 2 (Averbakh, 2006) (Azaron et al., 2006) 2 ~ ~ (Allahverdi, 2006) ~ ~ (Wang et al., 2005b) 2 2 ~ Problem (Soroush & Allahverdi, 2005) (Wang et al., 2005a) (Hong & Chuang, 2005) (Pawel Jan Kalczynski & Kamburowski, 2005) (Yang et al., 2004) (Gourgand et al., 2005) Reference , , , , ~ ~ , ~ ~ , , , , , , ̅ , ~ , ̅ , Hypothesis-test method incorporated into a genetic algorithm Simulation-optimization approach that hybridizes ordinal optimization, optimal computing budget allocation and a genetic algorithm Development of two dominance relations to obtain the set of dominant schedules Interval data min-max regret. Linear-time algorithm based on the geometric formulation of the problem without uncertainty Method for approximating the distribution function of the longest path length in the network of queues by constructing a proper continuous-time Markov chain The same coefficient of variation for all processing times. Extension of Johnson’s and Talwar’s rules. Algorithm based on the Johnson algorithm and a modification of McCahon and Lee’s approach. Assuming that the job processing times can be stochastically ordered on both machines, the authors show that the problem is equivalent to traveling salesman problem on a permuted Monge matrix and prove its NP-hardness Exact approaches Simulation-optimization with tabu search A theorem that provides a recursive scheme based on Markov chains and Chapman–Kolmogorov equations to compute the expected makespan. This scheme is combined with simulated annealing. Fuzzy Gupta algorithm Solution approach Modeling of uncertain parameters Fuzzy √ √ Probability Fuzzy √ √ √ √ √ √ Bounded √ Interval theory √ √ √ √ √ √ Robust √ √ √ √ Stochastic (not simulation) √ √ √ √ √ Simulation-optimization Approach taken to deal with uncertainty Optimization method √ √ √ √ √ Exact Table 3 Classification of the reviewed works (Continued) √ Heuristic 406 √ √ √ √ Metaheuristic 2 2 (Matsveichuk et al., 2009) (Ng et al., 2009) (Niu & Gu, 2008) (Gholami et al., 2009) (Nezhad & Assadi, 2008) (Javadi et al., 2008) , , , (Swaminathan et al., 2007) , , | Problem (Chen & Shen, 2007) (Alfieri, 2007) (Schultmann et al., 2006) Reference , | ~ ̅ , , ∑ | | , , 1 ∑ | | 1 1 , , , , , ∑ | | 1 ∑ | | ̅ . . Two phases: off-line and on-line scheduling. This set of dominant schedules allows an on-line scheduling decision to be made whenever additional local information on the realization of an uncertain processing time is available. Dominance. Dominance relation. Mathematical approach. Probabilistic asymptotic analysis of the problem, finding good results for two different non-delay algorithms Simulation-optimization with dispatching rules and genetic algorithms. The approaches studied are categorized as follows: pure permutation scheduling, shift-based scheduling, and pure dispatching for non-permutation sequences. Fuzzy multi-objective linear programming model. Fuzzification of the aspiration levels of the objectives. Method that approximates the maximum operator as a triangular fuzzy number with CDS algorithm Particle swarm optimization Simulation-optimization approach with genetic algorithm Fuzzy approach that delivers six schedules for the crisp problems. Although the six schedules are most probably not identical, the decision-maker receives optimal and good solutions for different membership levels Simulation-optimization approach with dispatching rules Solution approach Modeling of uncertain parameters Fuzzy Bounded √ √ √ √ Robust √ √ √ √ √ Stochastic (not simulation) √ √ √ √ √ √ √ Probability √ √ Fuzzy √ √ Simulation-optimization Approach taken to deal with uncertainty Optimization method √ √ Exact E. M. González-Neira et al. / International Journal of Industrial Engineering Computations 8 (2017) √ √ √ Heuristic Table 3 Classification of the reviewed works (Continued) √ √ √ √ √ Metaheuristic Interval theory 407 (Wang & Choi, 2010) (Paul & Azeem, 2010) (Geismar & Pinedo, 2010) (Diep et al., 2010) (Allahverdi & Aydilek, 2010b) (Allahverdi & Aydilek, 2010a) (Aydilek & Allahverdi, 2010) (Azadeh et al., 2010) (Sancar Edis & Ornek, 2009) (Yimer & Demirli, 2009) (Zandieh & Gholami, 2009) (Safari et al., 2009) Reference , ~ , , , ∑ | | , | Mixed-integer fuzzy programming model and a genetic algorithm solution approach Simulation-optimization approach with an immune algorithm Simulation-optimization approach with NEH heuristic, simulated annealing, and the genetic algorithm separately. Results show the superiority of the genetic algorithm. Simulation-optimization with tabu search √ √ √ √ 2 2 ~ ̅ | , , ~ ~ ∗ | Common environment in the microlithography portion of semiconductor manufacturing. The objective is to maximize throughput quantities, which is equivalent to minimizing the throughput times. Markov chains. Fuzzy due dates, cost over time, and profit rate, resulting in job priority. Grouping and sequencing algorithm. Decomposition-based approach to decompose the problem into several machine clusters. A neighboring K-means clustering algorithm is designed to group machines in clusters. Then a genetic algorithm or SPT rule generates the schedule for each machine cluster. Flexible artificial neural network–fuzzy simulation algorithm with dispatching rules Dynamic programming and a semi-Markov process. Eleven heuristics based on SPT rule √ √ √ 1 ~ Five heuristics ∑ | | , , 2 , , √ ~ ~ Fuzzy Fourteen heuristics , , , , Solution approach Bounded 2 , | Problem Modeling of uncertain parameters Probability √ √ √ √ Fuzzy √ √ Robust √ Stochastic (not simulation) √ √ √ √ √ √ Simulation-optimization Approach taken to deal with uncertainty Interval theory √ √ √ √ Optimization method √ √ √ √ √ Exact Table 3 Classification of the reviewed works (Continued) √ √ √ Heuristic 408 √ √ √ √ Metaheuristic