Márcia de Fátima Morais
State University of Paraná (UNESPAR), Brazil
E-mail: marciafmorais@yahoo.com.br
Thays Josyane Perassoli Boiko
State University of Paraná (UNESPAR), Brazil
E-mail: thaysaperssoli@bol.com.br
Leandro dos Santos Coelho
Federal University of Parana (UFPR), Brazil
E-mail: lscoelho2009@gmail.com
Rony Peterson da Rocha
State University of Paraná (UNESPAR), Brazil
E-mail: ronypeterson_eng@hotmail.com
Paulo Roberto Paraíso
State University of Maringá (UEM), Brazil
E-mail: paulo@deq.uem.br
Submission: 11/06/2014
Accept: 25/06/2014
ABSTRACT
This research focuses on the
Hybrid Flow Shop production scheduling problem, which is one of the most
difficult problems to solve. The literature points to several studies that
focus the Hybrid Flow Shop scheduling problem with monocriteria functions.
Despite of the fact that, many real world problems involve several objective
functions, they can often compete and conflict, leading researchers to concentrate
their efforts on the development of methods that take this variant into
consideration. The goal of the study is to review and analyze the methods in
order to solve the Hybrid Flow Shop production scheduling problem with
multicriteria functions in the literature. The analyses were performed using several
papers that have been published over the years, also the parallel machines
types, the approach used to develop solution methods, the type of method develop,
the objective function, the performance criterion adopted, and the additional
constraints considered. The results of the reviewing and analysis of 46 papers
showed opportunities for future research on this topic, including the
following: (i) use uniform and dedicated parallel machines, (ii) use exact and
metaheuristics approaches, (iv) develop lower and uppers bounds, relations of
dominance and different search strategies to improve the computational time
of the exact methods, (v) develop other types of metaheuristic, (vi) work with
anticipatory setups, and (vii) add constraints faced by the production systems
itself.
Keywords: Production
Scheduling; Multicriteria Functions; Hybrid Flow Shop; Literature.
1.
INTRODUCTION
Production
scheduling is one of the most complex activities in the management of
production systems. It is closely connected with the firm's performance in
terms of speed, reliability, flexibility, quality, and cost.
The
theory of production scheduling, that aims to provide guidelines and methods,
for efficient use of resources, has been the subject of countless papers, over
the past five decades (MORAIS; MOCCELLIN, 2010). Although several features of scheduling
problems are still underexplored due to the variety of production environments,
the available resources, restrictions may be imposed and there are multiple objectives
to be achieved.
Therefore,
this research aims to identify and quantify the published papers that present solution
methods for scheduling problems in Hybrid Flow Shop with multicriteria. The
results, of this research, may be useful for future research, towards the
development of new solution methods, and/or for the application of methods
investigated in the context of real companies, with this kind of scheduling problem.
In this article, the term multicriteria is used
generically to mean two or more criteria (bicriteria, tricriteria, and
multicriteria), which are processed simultaneously in the same objective
function.
It is noted that this research is dedicated solely to
the production scheduling of jobs, not dealing with the production scheduling
of batches of jobs.
This
paper is structured in six sections. After the presentation of the context and research
objectives, the theoretical framework is explained in Section 2. In Section 3,
the research methodology is presented. Then, the papers that present solution
methods for the multicriteria Hybrid Flow Shop scheduling problem are cited. An
analysis of papers is presented in Section 5; followed by conclusions, and final
considerations, in the sixth section.
2.
THEORETICAL FRAMEWORK
2.1 Production Scheduling
Problem
Production scheduling is one
of the activities of the Planning, Programming and Production Control. This is
responsible for deciding the allocation of resources (called machines) over
time to perform individual items (jobs and/or batch of jobs, called jobs), in
order to better meet a predefined set of criteria (BAKER, 1974, MACCARTHY; LIU, 1993, YANG; LIAO, 1999,
and PINEDO, 2008).
One can understand the production scheduling as a set
of functions of decision-making, involving: i) allocation decisions machines to
process jobs over time (Baker, 1974), called schedule (PINEDO, 1995); ii)
decisions sequencing jobs (Baker, 1974), called sequence, which correspond to
the order in which jobs are processed on a given machine (PINEDO, 1995).
Therefore, a scheduling problem is “a problem of n jobs {J1, J2,
..., Jj, ..., Jn}
that must be processed on m machines
available {M1, M2, ..., Mk, ..., Mm}” (FRENCH, 1982, p. 5). I.e.,
a scheduling problem “…consists of determining the order or sequence in which
the machines will process the jobs so as to optimize some measure of
performance” (JOHNSON; MONTGOMERY, 1974, p.322).
Due
to the complexity related to obtaining and maintaining production schedules in
firms, this activity is a major obstacle in the search for a good performance
of production processes. In fact, the scheduling problem is among the most
difficult problems of resolution (MORAIS; MOCCELLIN, 2010).
Based
on MacCarthy; Liu (1993), Allahverdi; Cheng; Kovalyov (2008), and Pinedo
(2008), lists the following types of scheduling environments: single machine;
parallel machine; flow shop; permutational flow shop; job shop;
hybrid flow shop or flow shop with multiple machines; hybrid job shop or
job shop with multiple machines, and; open shop. Figure 1 presents the
relationship between these environments.
Figure 1: Environments of
scheduling and their relationships
Source: MacCarthy; Liu (1993)
This
research is dedicated to the Hybrid Flow Shop.
2.2
Hybrid Flow Shop
It is difficult to find a general definition for
Hybrid Flow Shop; however, for the purposes of this research, presented by
Sethanan (2001) the following is appropriated.
The
Hybrid Flow Shop is a type of flow shop in which, at least one of the k stages of production, the number of
machines is greater than 1 (k < m). In the stages that the number of
machines is greater than 1, there are k
machines or processors in parallel, and each jobs is processed on only one
machine stage (SETHANAN, 2001). Figure 2 illustrates the Hybrid Flow Shop scheduling
environment.
According
to Burtseva; Yaurima; Parra (2010), the possible machine set environments in
stage i of a Hybrid Flow Shop are the
following:
·
Identical (ID) machines in parallel: the mi machines in the set have
the same speed; therefore, job j may
be processed on any of mi
machines, since the job processing time is the same for all machines;
·
Uniformed (UN) machines in parallel: the mi machines in the set have
different speeds; a job j may be
processed on any machine of a set; however, its processing time is proportional
to the machine speed;
·
Unrelated (UR) machines in parallel: the mi machines in the set have
different speeds; a job j may be
processed on any machine of a set; however, its processing time, reveals not to
be proportional to the speed of the machine;
·
Dedicated (DED) machines in parallel: the mi machines in the set are
dedicated to perform specific jobs, performing specific jobs.
Figure 2: Hybrid Flow Shop scheduling
environment
Source: Morais (2008)
2.3 Performance Criteria
in Scheduling Problems
The production
scheduling is always carried out in order to reach a criterion or set a
performance criteria that characterize the nature of the scheduling problem
(BOIKO; MORAIS, 2009). Based on French (1982), Bedworth; Bailey (1987),
MacCarthy; Liu (1993), Morton; Pentico (1993), and Pinedo (2008), the Table 1
presents the performance criteria, adopted in scheduling problems.
These
different performance criteria, according to Baker (1974), relate to three
types of decision-making:
i) Efficient
use of resources;
ii) Rapid response to demand, and;
iii) Adaptation to prescribed deadlines of a job
that, if reached, cancels the processing that has already been accomplished.
Table 1: Performance Criteria adopted in scheduling
problems
Regarding
the optimization criteria Lateness and Tardiness, Pinedo (2008) explains the
delay of job j (Lateness - Lj) the difference between the completion
time of job and its due date, is defined as Lj = Cj – dj,
while the delay of job j (Tardiness - Tj) corresponds to the delay
in completing the job in relation to its due date. According to Pinedo (2008)
Tardines of job is defined as Tj = max(Cj – dj,
0) = max(Lj, 0). The difference between Tardiness and Lateness lays
on the fact that Tardiness is never negative.
In
addition to performance criteria, mentioned above, according to Godinho Filho
et al. (2013) other criterias have been reported in the literature: Due Date
Cost (Σcjdj); Bottleneck Utilization
Rate (BTK); Capacity Utilization Rate (CPT); Inventory Costs (IC); Number of
Families (NF); Overtime (OT); Size Buffer (SB); Time Blocking of the Machines
(MBT); Total Cost of Opportunity (TCO); Total Cost of Setup (TSC); Total Cost
Utility (TCU); Total Idle Time (MIT); Total Setup Time (TST ou ΣSj);
Transportation Costs (TC); Work In Process (WIP).
2.4 Constraints
in Scheduling Problems
Regarding
to the assumptions of scheduling problems, these can be divided into hypotheses
about jobs and/or job groups, about machinery and policy operations (GUPTA;
STAFFORD, JR., 2006). These assumptions determine the constraints of a specific
scheduling problem, in order to make the problem as similar as possible to a real
situation.
Based on Allahverdi et al. (1999), Allahverdi et al
(2008), and Pinedo (2008), Table 2 presents the constraints that may be
incorporated in scheduling problems; as well as the notation adopted in this
article to describe these constraints.
In addition to these constraints, single machine is a
special case in which many stages (not all) in a Hybrid Flow Shop can have only
one machine (BURTSEVA; YAURIMA; PARRA, 2010); this environment is termed as
Hybrid Flow Shop with a dominant stage (MORAIS; GODINHO FILHO; BOIKO, 2013).
Table 2: Constraints incorporated in scheduling
problems.
2.5 Solution
Methods
Since
the pioneering work of Johnson, published in 1954 (JOHNSON, 1954), many
solution methods have been developed to solve the scheduling problems in many
different types of scheduling environments.
According to Yenisey; Yagmahan (2014), the solution
methods for scheduling problems can be categorized into:
·
Optimum or exact methods: methods that generate an
optimal schedule, according to the performance criterion adopted; mathematical
models and specific algorithms are used to solve problems, and obtain an
optimal solution, as it adds Pereira (2011);
·
Approximate methods: methods that seek to achieve a
feasible solution close to the optimum in a reasonable computational time; can
be classified, according to Yenisey; Yagmahan (2014), into heuristic and metaheuristic.
The
use of optimum methods is justified when dealing with small problems; the
solution for problems, using optimum methods, usually demand high computational
time, making the search for optimal solutions not viable (PEREIRA, 2011). Thus,
Yenisey; Yagmahan (2014) add that, the optimum methods become inefficient for
large problems, since they have many jobs, machines and goals, and are
combinatorial optimization problems from NP-hard problems class. Arenales et
al. (2007) emphasize that the development of integer programming softwares,
such as CPLEX, XPRESS, and LINDO, has improved their ability to solve large
problems. The Branch-and-Bound (B&B) method is the approach, according to Yenisey;
Yagmahan (2014), most commonly, used to obtain optimal solutions. Arenales et al. (2007) also points the
Branch-and-Cut (B&C), Gomory, Benders, Dantzig-Wolf, and Lagrangian
Relaxation to obtain optimal solutions.
Heuristics
are methods that generate a schedule of good quality at a reasonable
computational time, with no guarantee of optimality. Solutions obtained by
heuristics can be used as an initial solution in improving heuristics and
metaheuristics. According to Souza; Moccellin (2000) heuristics can be subclassified
into:
·
Constructive heuristic: the schedule, adopted as the
problem solution, is obtained: i) directly from the ordering of jobs by
priority indexes, calculated according to the processing times of the jobs; ii)
by sorting the best schedule jobs, from a set of schedules obtained, also using
priority indexes associated with the jobs, or; iii) from the successive
generation of partial schedules jobs, to obtain a complete schedule through
some criterion insertion of jobs, and;
·
Improvement heuristic: the schedule, adopted as the
problem solution, is obtained from initial solutions that, through some
iterative procedure (usually involving exchanges of positions jobs in original
schedule), are improved, seeking to achieve a better solution, than the current
one, according as the performance criterion adopted.
·
Metaheuristics
are procedures that coordinate local search strategies at a higher level,
creating a process to avoid local minimum, conducting a search of the most
robust solution to a problem (GLOVER; KOCHENBERGER, 2003); although there is no
consensus in the literature concerning a standard subclassification of
metaheuristic, this can be used
(PEREIRA, 2011; OLIVEIRA, 2008; and SERAPIÃO, 2009):
·
Metaheuristics of relaxation: “…procedures to solve
problems with modifications to the original model, the generated solution provides
the solution to the original problem.” (PEREIRA, 2011, p. 6).
This kind of metaheuristics simplifies the real problem, removing and modifying
some restrictions of it (OLIVEIRA, 2008).
·
Metaheuristics of neighborhood search: “… procedures
that run search spaces, which should be considered at each step, the
neighborhood of the solution obtained in the previous interaction.” (PEREIRA,
2011, p. 16); e.g., according to Blum; Roli (2003), Dreo et al. (2007) and
Yenisey; Yagmahan (2014) are: Greedy Randomized Adaptive Search Procedure
(GRASP); Tabu Search (TS); Guided Local Search (GLS), Iterated Local Search
(ILS), Local Search (LS), and, Variable Neighborhood Search (VNS).
·
Metaheuristics based on evolutionary methods:
“…procedures focused on sets of solutions that evolve in this space.” (PEREIRA,
2011, p. 16); e.g., according to Dreo et al. (2007), Simon (2013)
and Yenisey; Yagmahan (2014) : Genetic Algorithm (GA); Estimation of
Distribution Algorithm (EDA); Differential Evolution (DE); Memetic Algorithm
(MA); Simulated Annealing (SA); Scarter Search (SS); Artificial Immune System
(AIS); Colonial Competitive Algorithm (CCA);.and Harmorny Search Optimization
(HSO),
·
Metaheurisitcs based on swarm intelligence: procedures
based on swarm intelligence include any attempt to design algorithms in order
to solve problems inspired by the collective behavior of social insects and
other animal societies (BONABEAU; DORIGO;
THERAULAZ, 1999). Examples of methods based on swarm intelligence are: Ant
Colony Optimization (ACO); Particle Swarm Optimization (PSO); Artificial Bee
Colony (ABC); Firefly Algorithm (FA); Shuffled Frog-Leaping (SFL); and Bacterial Foraging
Optimization (BFO) (SERAPIÃO, 2009 and RUIZ-VANOYE, 2012);
·
Hybrids metaheuristics: “…procedures that combine two
or more metaheuristics and uses search strategies.” (PEREIRA, 2011, p. 16).
Boschetti
et al. (2009) adds and emphasizes the use of hybrid methods or matheuristics,
algorithms that are developed from the interoperation of metaheuristics and
mathematical programming techniques.
3.
RESEARCH
METHODOLOGY
The
methods qualitative and quantitative were used in this research. For the
purpose, this research was classified as descriptive, explanatory,
methodological, and as bibliographical.
The
databases used in the literature review were: Compendex; Digital Library of
Theses and Dissertations; DOAJ; Emerald; Hindawi, Open J-Gate; IEEE Xplore;
Science Direct; Web of Knowledge; Scielo and; Brazilian Digital Library (BDTD);
Scirus, and; Scopus. The keywords used were: flow shop; hybrid flow shop;
flexible flow shop; multiple machines flow shop; flow shop with multiple
machines; bi-objective; tri-objective, multi-objective; bicriteria; tricriteria,
and; multicriteria. An extensive combination of keywords was also used to
identify the published papers. A time limitation has not been established.
For each paper, the following topics were
reviewed:
i)
The machine set environments in Hybrid Flow Shop
considered: identical (ID); uniform (UN); unrelated (UR), or; dedicated (DED);
ii)
The performance criteria adopted;
iii)
The considered constraint(s);
iv)
Objective function used: bicriteria; tricriteria; multicriteria;
v)
Solution method(s) developed, in terms of:
-
Methods categories: optimum methods; approximate
methods;
-
Approximate methods classification: heuristic;
metaheuristic;
-
Heuristics subclassification: constructive;
improvement;
-
Metaheuristics subclassification: neighborhood search;
evolutionary; swarm intelligence; hybrids;
-
Optimum method type developed;
-
Metaheuristic type developed.
Analyses
were made based on the number of publications and percentage of occurrence.
In the review, only papers that consider the performance
criteria simultaneously, in the same objective function, were reviewed.
4. MULTICRITERIA HYBRID FLOW SHOP SCHEDULING PROBLEM: LITERATURE REVIEW
A literature review on the development of solution methods
for the bicriteria, and multicriteria scheduling problem was presented by Nagar,
Heragu & Haddock (1995); but, the authors did not identify the publications
addressing the Hybrid Flow Shop scheduling problem.
Several papers that address the Hybrid Flow Shop
scheduling problem with two or more performance criteria have been identified, however,
many of these papers deal with the development and analysis methods for each
criterion separately.
In
the review, 46 articles that simultaneously consider the performance criteria
found: Hayrinen et al. (2000); Liu; Chang (2000); Janiak; Lichteinsten (2001); Gupta
et al. (2002); Tang et al. (2002); Lin;
Liao (2003); Jungwattanaki et al. (2005); Quadt; Kuhn (2005); Sawik (2005); Akrami;
Karimi; Hosseini (2006); Torabi; Fatemi-Ghomi;
Karimi (2006); Janiak et al. (2007); Jenabi et al. (2007); Jungwattanaki et al.
(2007); Quadt; Kuhn (2007); Sawik (2007); Xuan; Tang (2007); Fakhrzad; Heydari
(2008); Jungwattanaki et al. (2008); Khalouli; Ghedjati; Hamzaoui (2008); Mahdavi
et al. (2008); Behnamian; Fatemi Ghomi; Zandieh (2009); Davoudpour; Ashrafi
(2009); Jungwattanaki et al. (2009); Naderi; Zandieh; Roshanaei (2009); Naderi
et al. (2009), Weng; Fujimura (2009a); Weng; Fujimura (2009b); Behnamian;
Zandieh; Fatemi Ghomi (2010); Dugardin; Yalaoui; Amodeo (2010); Karimi; Zandieh; Karamooz
(2010); Khalouli; Ghedjati; Hamzaoui (2010); Li; Wang; Huo (2010); Rashidi;
Jahandar; Zandieh (2010); Behnamian; Zandieh (2011); Cho et al. (2011); Li et
al. (2011); Mousavi; Zandieh; Amiri (2011); Pereira (2011); Zandieh; Karimi
(2011); Han et al. (2012); Weng; Wei; Fujimura (2012); Bozorgirad; Logendran
(2013); Ebrahiny; Fatemi Ghomi; Karimi (2013); Fadaei; Zandieh (2013); and
Jolai et al. (2013).
In
addition to what was related above, Sang (2013) points out problems on the
mixed integer programming model to Hybrid Flow Shop scheduling proposed by Behnamian; Zandieh (2011). Tables 3:
summarizes the main points reviewed in every paper.
Table 3: Papers that presents solution methods for
multicriteria Hybrid Flow Shop scheduling problem – Review Summary
Papers |
The machine set environments |
Performance Criterions |
Constraints |
Objective Function |
Solution methods |
|
Category and Classification |
Sub Classification or Type |
|||||
Hayrinen et al. (2000) |
UR |
∑Tj; ∑Wj; IBS; NF |
STsd-NS Lostop |
Multicriteria |
- Approximate:
i) Heuristic |
i) Improvement |
Liu; Chang (2000) |
ID |
TST; TSC |
STsd-NS |
Bicriteria |
- Optimum |
MIP
and Rel_Lag |
Janiak;
Lichteinsten (2001) |
ID |
∑wjEj;
∑wjTj; ∑wjWj |
- |
Tricriteria |
- Approximate: i) Heuristic |
i)
Constructive |
Gupta et al. (2002) |
ID |
∑Ej; ∑Tj; Cmax; ∑cjdj |
- |
Multicriteria |
- Approximate: i) Heuristic; ii) Metaheuristic |
i) Constructive; ii) Neighborhood Search: LS |
Tang et al. (2002) |
ID |
∑wjEj; ∑wjTj |
Batch Prec STsi-NS Removal |
Bicriteria |
- Optimum; - Approximate: i) Heuristic |
MIP and Rel_Lag/PD i) Improvement |
Lin; Liao (2003) |
DED |
∑Wj;
∑OT |
Batch STsd-NS |
Bicriteria |
- Approximate: i) Heuristic |
i)
Improvement |
Jungwattanaki et al. (2005) |
UR |
Cmax; ∑Uj |
STsd-NS |
Bicriteria |
- Approximate: i) Heuristic; ii) Metaheuristic |
i) Constructive; ii) Evolutionary: GA and SA |
Quadt; Kuhn (2005) |
ID |
TSC; IC; ∑cjUj; ∑Fj/n |
Batch |
Multicriteria |
- Approximate: i) Heuristic |
i)
Constructive |
Sawik (2005) |
ID |
∑Uj; ∑Tj; Tmax; TWR |
Batch Zbfr H_Fin |
Multicriteria |
- Optimum |
MIP |
Akrami; Karimi;
Hosseini (2006) |
ID |
TSC; ∑Fj/n |
Batch STsi-NS Zbfr H_Fin |
Bicriteria |
- Optimum - Approximate: i) Metaheuristc |
MIP i) Neighborhood Search: TS; and Evolutionary:
GA |
Torabi; Fatemi-Ghomi; Karimi (2006) |
ID |
TST; TC; WIP; IC |
Batch STsi-NS H_Fin |
Multicriteria |
- Optimum - Approximate: i) Metaheuristc |
MIP i)
Evolutionary: GA |
Janiak et al. (2007) |
ID |
∑wjEj; ∑wjTj;
∑wjWj |
- |
Tricriteria |
- Approximate: i) Metaheuristc |
MIP i) Neighborhood Search :TS; Evolutionary: SA; and Hybrid: TS/SA |
Jenabi et al. (2007) |
UR |
TST; CE |
Batch STsi-NS H_Fin Skp_Stage |
Bicriteria |
- Optimum - Approximate: i)
Heuristic; ii) Metaheuristc |
MIP i) Constructive ii) Hybrid: GA/SA |
Jungwattanaki et al. (2007) |
UR |
Cmax; ∑Uj |
STsd-NS |
Bicriteria |
- Approximate: i) Heuristic; |
i) Constructive |
Quadt; Kuhn (2007) |
ID |
TSC; ∑Fj/n |
Batch STsi-AS Skp_Stage |
Bicriteria |
- Approximate: i) Metaheuristc |
i)
Evolutionary: GA |
Sawik (2007) |
ID |
∑Uj; CPT |
Zbfr H_Fin |
Bicriteria |
- Optimum - Approximate: i) Heuristc |
MIP i)
Contructive |
Xuan; Tang (2007) |
ID |
∑wjCj; ∑wjWj |
STsi-NS Transport Lostop Prec |
Bicriteria |
- Optimum |
Rel_Lag |
Fakhrzad; Heydari (2008) |
ID |
∑cjEj; ∑cjTj |
STsi-NS Btlck Lrem |
Bicriteria |
- Optimum - Approximate: i) Heuristc;
ii) Metaheuristic |
MIP i) Constructive ii) Neighborhood Search: TS; Evolutionary: SA; and Hybrid: SA/TS |
Jungwattanaki et al. (2008) |
UR |
Cmax; ∑Uj |
STsd-NS Diff_rj |
Bicriteria |
- Approximate: i) Heuristc;
ii) Metaheuristic |
i) Constructive ii) Evolutionary: GA |
Khalouli; Ghedjati; Hamzaoui (2008) |
ID |
∑wjEj; ∑wjTj |
- |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Swarm Intelligence: ACO |
Mahdavi et al. (2008) |
ID |
∑wjTj; ∑wjLj |
Batch STsi-NS |
Bicriteria |
- Optimum - Approximate: i) Metaheuristic |
MIP i) Evolutionary: GA |
Behnamian; Fatemi Ghomi; Zandieh (2009a) |
ID |
Cmax; ∑Lj; ∑Tj |
STsd-NS |
Tricriteria |
- Approximate: i) Metaheuristic |
i) Hybrid: GA/LS/SA/VNS |
Behnamian; Zandieh; Fatemi Ghomi (2009b) |
ID |
∑Ej; ∑Tj |
Batch STsd-NS Window_dj |
Bicriteria |
- Approximate: i) Metaheuristic |
i) Neighborhood Search: VNS;
and Evolutionary: SA; and Swarm Intelligence: PSO |
Davoudpour; Ashrafi (2009) |
ID |
Tmax; ∑Cj; Lmax; ∑wjTj |
STsd-NS Diff_rj |
Multicriteria |
- Approximate: i) Metaheuristic |
i)
Neighborhood Search: GRASP |
Jungwattanaki et al. (2009) |
UR |
Cmax; ∑Uj |
STsd-NS Skp_Stage |
Bicriteria |
- Approximate: i) Heuristc;
ii) Metaheuristic |
i) Constructive i)
ii) Neighborhood Search: TS; and Evolutionary: GA and SA. |
Naderi; Zandieh; Roshanaei (2009) |
ID |
Cmax; Tmax |
STsd-NS |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Hybrid: SA/LS |
Naderi et al. (2009) |
ID |
Cmax; ∑Tj |
STsd-NS Transport |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Hybrid: SA/LS |
Weng; Fujimura (2009a) |
UR |
∑Ej; ∑Tj |
- |
Bicriteria |
- Approximate: i) Heuristic |
i)
Improvement |
Weng; Fujimura (2009b) |
ID |
∑wjEj; ∑wjTj |
- |
Bicriteria |
- Approximate: i) Heuristic |
i)
Constructive |
Dugardin; Yalaoui;
Amodeo (2010) |
ID |
BTK; Cmax |
Dom_Estage Reentrant |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Karimi; Zandieh; Karamooz (2010) |
ID |
Cmax; ∑Tj |
Batch STsd-NS Skp_Stage |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Khalouli; Ghedjati; Hamzaoui (2010) |
ID |
∑wjEj; ∑wjTj |
- |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Swarm Intelligence: ACO |
Li; Wang; Huo (2010) |
ID |
∑Wj; MIT |
STsd-NS |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Rashidi; Jahandar; Zandieh (2010) |
UR |
Cmax; Tmax |
STsd-NS Block |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Behnamian; Zandieh (2011) |
ID |
∑Ej; ∑Tj2 |
STsd-NS L_WT |
Bicriteria |
- Optimum - Approximate: i) Metaheuristic |
MIP i)
Evolutionary: CCA |
Cho et al. (2011) |
ID |
Cmax;∑Tj |
Reentrant |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Li et al. (2011) |
ID |
Cmax;∑Tj |
STsd-NS |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Mousavi; Zandieh; Amiri (2011) |
ID |
Cmax;∑Tj |
STsd-NS |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
i) Neighborhood Search: VNS |
Pereira
(2011) |
ID |
∑wjEj; ∑wjTj |
STsd-NS Diff_rj |
Bicriteria |
- Optimum - Approximate: i) Metaheuristic |
MIP i)
i) Neighborhood Search: ILS;
Evolutionary: GA ; and Hybrid: GA/LS |
Zandieh;
Karimi (2011) |
ID |
∑wjTj; Cmax |
Batch STsd-NS |
Bicriteria |
- Optimum - Approximate: i) Metaheuristic |
MIP i) Evolutionary: GA |
Han et al. (2012) |
ID |
∑wjEj;∑wjTj |
- |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Hybrid: PSO/DE |
Weng;
Wei; Fujimura (2012) |
UR |
∑Ej; ∑Tj |
Dyn_Arr |
Bicriteria |
- Approximate: i) Heuristic |
i)
Constructive |
Bozorgirad; Logendran (2013) |
UR |
WIP; ∑Tj |
Batch STsd-NS |
Bicriteria |
- Optimum - Approximate: i) Metaheuristic |
MIP i)
i) Neighborhood Search: TS |
Ebrahiny; Fatemi Ghomi; Karimi (2013) |
ID |
Cmax;∑Tj |
STsd-NS Stoc_dj |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Fadaei; Zandieh (2013) |
ID |
Cmax; ∑Tj |
Batch STsd-NS |
Bicriteria |
- Approximate: i) Metaheuristic |
i)
Evolutionary: GA |
Jolai et al
(2013) |
ID |
Cmax;Tmax |
No-wait |
Bicriteria |
- Optimum - Approximate: i) Metaheuristic |
MIPi) Evolutionary:
SA |
5. MULTICRITERIA HYBRID FLOW SHOP SCHEDULING PROBLEM: LITERATURE ANALYSES
Methods for
the multicriteria Hybrid Flow Shop (HFS) were found in 46 papers.
Figure 3
shows the number of papers published per year, and Figure 4 shows the evolution
of research in multicriteria HFS scheduling problem.
Figure 3: Number of publicarions per year in multicriteria
HFS scheduling problem
Figure 4: Evolution
of research in multicriteria HFS scheduling problem
When analyzing
Figure 4, it can be seen that, although in some years the number of
publications decreased, there is a growth trend in the researches in multicriteria HFS.
Figure 5: Machines types in parallel used for developing solution
methods for multicriteria HFS
Restrictions
are present in 38 papers (82.60%):
·
Setup times restrictions are the ones that appears
more, being considered in 81.57% (31 papers) of these papers; dependent and
non-anticipatory setup are present in 23 works (74.19% of papers with setup
times restrictions); while independent and non-anticipatory setup are present
in 7 works (22.59% of papers with setup times restrictions); of papers with setup
times restrictions, only Quadt; Kuhn (2007) investigate the development of solution
methods with anticipatory setup;
·
Batch sizes and scheduling restrictions are present in
36.84%;
·
Finite horizon scheduling restrictions, in 13.15%;
·
Jobs that can skip stages restrictions are considered
in 10.52%;
·
Limited buffers and different release dates restrictions
appear in 7.89%;
·
Lost operations, precedence, transport time, and
reentrant flow restrictions are present in 5.26% of papers each;
·
Blocking, removal times, no-wait, stochastic due
dates, window due dates, remaining level of resources, resource bottleneck,
dominant stage, dynamic arrival of jobs, and limited waiting time restrictions were seen in 2.63% of the papers each.
From
the 46 papers, 37 papers (80.43%) address the development of methods with
bicriteria function; 3 papers (6.52%) work with the development of methods with
a tricriteria function, and; 6 papers (13.04%) address the development of
methods with multicriteria function.
Concerning
the bicriteria functions, performance criteria related to delayed jobs (ΣTj,
ΣwjTj, Tmax, ΣUj, and ΣWj
), combined with other criteria, appear in 19 papers (51.35%); Makespan (Cmax)
is present in 16 papers (43,24%); the criteria oriented just-in-time scheduling
(∑wjEj and ∑wjTj, ∑Tj
and ∑Ej, ∑cjEj, and ∑cjTj)
appear in 12 papers (35.29%); Total Setup Cost (TSC) criteria are present in 3
papers (8.10%); Total Setup Time (TST) and Mean Flow Time (∑Fj/n) are
adopted in 2 papers each (5.40%); others criteria, as Bottleneck Utilization
Rate (BTK), Capacity Utilization Rate (CPT), Inventory Cost (IC), Overtime
(OT), Total Idle Time (MIT), and Work-In-Process (WIP) appear in 1 paper each
(2.70%).
Regarding
the tricriteria functions, earliness, tardiness, and waiting time (∑wjEj,
∑wjTj and ∑wjWj) criteria appear in
2 papers simultaneously (66.66%); Lateness, makespan, and Tardiness (Cmax,
∑Lj and ∑Tj) are present in 2 papers simultaneously
(33.33%).
In
the papers that adopt a multicriteria function, the following performance
criteria are considered: Internal Buffer Size (IBS);
Inventory Cost (IC); Lateness Maximum (Lmax); Makespan (Cmax);
Maximum Tardiness (Tmax); Mean Flow Time (∑Fj/n); Number
of Families (NF); Number of Late Jobs (ΣUj); Tardy Work Ratio (TWR);
Total Completion Time (ΣCj); Total Earliness (∑Ej); Total
Lateness (ΣLj); Total Setup Cost (TSC); Total Setup Time (TCT); Total Tardiness
(ΣTj); Total Waiting (∑Wj); Transport Cost (TC); Weighted
Due Date of Jobs (Σcjdj); Weighted Number of Late Jobs
(ΣcjUj); Weighted Total Tardiness (ΣwjTj),
and; Work-In-Process (WIP). The performance criteria related to delayed
or advances of jobs (ΣTj, ΣwjTj, Tmax,
Lmax, ΣEj, ΣUj and ΣWj), combined
with others criteria, stand out as the performance criteria most frequently
adopted (83.33%).
Regarding
the solution methods developed, in terms of methods categories, it was found
that 30 papers (65.21%) presents approximate methods; 3 papers (6.52%) presents
optimum methods, and; 13 (28.26%) presents methods in both categories.
It
stands out that, several papers that present methods in both categories, do not
address the development of optimum methods. These papers present only mixed
integer programming formulations, that are solved by specific solvers (i.e.,
CPLEX), and their results provide parameters to evaluate the approximate
methods developed.
Considering
both papers that describe only the approximate methods as those present methods
in both categories, the vast majority develop metaheuristics, present in 33 papers
(71.73%); heuristics appear in 16 (34.78%).
Concerning
the heuristics subclassification, from the 16 papers, that investigates the
development of heuristics, 12 papers (75%) deal with the development of
constructive heuristics, and; 4 (25%) deal with the development of improvement
heuristics.
Concerning
the metaheuristic subclassification, from the 33 papers that present
metaheuristics, 10 papers (30.30%) present metaheuristics of neighborhood
search; 21 (63.63%) presents metaheuristics based on evolutionary methods; 3
(9,09%) presents metaheuristics based on swarm intelligence; and; 8 papers
(24.24%) presents hybrids metaheuristics.
From
the papers which present metaheuristics, it was observed that several papers
develop more than one type of method; the Genetic Algorithm stands out as one
of the methods that is most often adopted, being present in 19 papers (57.57%);
Simulated Annealing appears in 10 papers (30.30%); Tabu Search appear in 5 (15.15%);
Local Search in 5 (15.15%); Variable Neighborhood Search appears in 3 papers
(9,09%); Ant Colony Optimization, and Particle Swarm Optimization appear in 2
papers each (5,88%), and; Colonial Competitive Algorithm, Differential
Evolution, Greedy Randomized Adaptive Search Procedure, and Iterated Local
Search appear in 1 each (6.06%).
In
relation to papers that address the development of hybrids metaheuristics,
solution methods that combine Tabu Search and Simulated Annealing are presented
by Janiak et al (2007), and Fakhrzad; Heydari (2008); Local Search combined
with Simulated Annealing is presented by Naderi; Zandieh; Roshanaei (2009), and
Naderi et al. (2009); Local Search combined with Genetic Algorithm is presented
by Pereira (2011); Genetic Algorithm with Simulated Annealing is presented by Jenabi;
Fatemi Ghomi; Karimi (2007); Genetic Algorithm with Local Search, Simulated
Annealing and Variable Neighborhood Search is presented by Behanamian; Fatemi
Ghomi; Zandieh (2009); one solution method that combines Swarm Optimization
with Differential Evolution is presented by Han et al. (2012).
Concerning
the optimum method type, from the 15 papers, 12 papers (80%) present and
discuss the development of methods based only on programming linear and
non-linear mathematical formulations, according to the characteristics of the problems
under study; only 3 papers (20%) present mathematical formulations and discuss
the development of methods based on Lagrangian Relaxation and Dynamic Programming.
Figure
6 shows the percentage of papers by solution method(s) developed.
Figure 6: Multicriteria Hybrid Flow Shop scheduling problem – Percentage
of papers by solution method(s)
developed
6. CONCLUSIONS
This
article reviews the literature for multicriteria Hybrid Flow Shop (HFS)
scheduling problem. 46 articles, published between 2000 and 2013, were found.
The papers were reviewed in terms of the following:
the machine set environments in HFS considered; performance criteria adopted;
constraint(s) considered; objective function used, and; solution method(s)
developed, in terms of methods categories, approximate methods classification,
heuristics subclassification, metaheuristic subclassification, optimum method
type developed, and metaheuristic type developed.
The
analysis on the number of publications over the years shows that there is a
trend of growth in the researches in multicriteria HFS scheduling problem. It was not possible to compare the percentage
growth in the number of papers published for decades, because the first paper
addressing this problem was published in 2000.
Regarding
to the machine set environments
in HFS considered, identical parallel machine is present in the most papers;
only 1 paper treats the HFS scheduling problem with dedicated parallel
machines, and; uniform parallel machines are not treated in any article. In
practice, with
the exception of newly installed plants, the presence of identical parallel
machines is
not observed with frequency; since the acquisition of machinery in different
periods of time, the technological innovations have caused improvements in the
capabilities of the same.
The
results also showed that, most of the papers are devoted to development of
metaheuristics solution methods. Among the metaheuristics, the development of
Genetic Algorithms and their variations stands out.
Regarding
papers that present heuristics, it was found that constructive heuristics are
the focus of a considerable percentage of them.
Among
all the papers that present optimum methods, none of them dealt with the
development of lower and upper bounds, dominance relationships and search
strategies.
In
respect of performance criteria the presence of multiple goals in real
production environments were considered. Despite the fact that studies, considering
more than two performance criteria in the development of solution methods for
the HFS scheduling problem were found. Only 9 papers (19.56% of works) adopted three
or more performance criteria in the objective function.
The performance
criteria related to delayed jobs (ΣTj, ΣwjTj,
Tmax, ΣUj and ΣWj) stands out as one of the
performance criteria that are most often adopted. The criteria oriented
just-in-time scheduling (∑wjEj and ∑wjTj,
∑Tj and ∑Ej, ∑cjEj and ∑cjTj)
and were also present in a large number of papers.
Notably,
the vast majority of papers include constraints; however, many constraints were
not investigated. A new research that considers several constraints is needed,
to diminish the gap between the real-world industrial scheduling problems and
their treatment in the literature. The most common restrictions are setup
times. However, only one paper deals with anticipatory setups.
The
analyzes show that, future research may follow different approaches: i) focus
on the multicriteria HFS scheduling problems with uniformed and/or dedicated
machines in parallel; ii) develop optimum methods to solve multicriteria HFS
scheduling problems; iii) develop metaheuristics to solve multicriteria HFS
scheduling problems and still not very addressed in literature, such as
metaheuristics based on computation evolutionary and swarm intelligence; iv)
develop lower bounds and uppers bounds, relations of dominance and different
search strategies to obtain solutions for large multicriteria HFS scheduling
problems, with reduced computational time; v) investigate the multicriteria HFS
scheduling problems with several constraints, present in industries real-world
and ignored in the literature, such as anticipatory setups.
7. REFERENCES
AKRAMI,
B.; KARIMI, B.; MOATTAR-HOSSEINI, S. M. (2006) Two metaheuristic methods for the
common cycle economic lot sizing and scheduling in flexible flow shops with
limited intermediate buffers: the finite horizon case. Applied Mathematics and Computation, v.183, n.1, p. 634–645.
ALLAHVERDI,
A.; CHENG, T. C. E.; KOVALYOV, M. Y. (2008) A survey of scheduling problems
with setup times or costs. European
Journal of Operational Research, v. 187, p. 985–1032.
ALLAHVERDI,
A.; GUPTA, J. N. D.; ALDOWAISAN, T. (1999) A review of scheduling research
involving setup considerations. Omega - The
International Journal of Management Science, v. 27, p. 219-239.
ARENALES, M.;
ARMENTANO, V.; MORABITO, R.; YANASSE, I. (2007) Pesquisa Operacional. Rio de Janeiro: Elsevier.
BAKER,
K. R. (1974). Introduction to sequencing
and scheduling. New York: John
Wiley & Sons, Inc.
BEDWORTH, D. D.;
BAILEY, J. E. (1987). Integrated Production Control Systems: management, analysis, design. 2 ed.
New York: John Wiley & Sons, Inc.
BEHNAMIAN,
J.; FATEMI GHOMI, S.M.T.; ZANDIEH, M. (2009a) A Multi-phase covering
Pareto-optimal front method to multi-objective scheduling in a realistic hybrid
flowshop using a hybrid metaheuristic. Expert
Systems with Applications, v. 36, n. 8, p. 11057-11069.
BEHNAMIAN,
J.; ZANDIEH, M.; FATEMI GHOMI, S. M. T. (2009b) Due window scheduling with
sequence-dependent setup on parallel machines using three hybrid metaheuristic
algorithms. International Journal
Advanced Manufacture Technology, v. 44, p. 795–808.
BEHNAMIAN, J.;
ZANDIEH, M. (2011) A
discrete colonial competitive algorithm for hybrid flowshop scheduling to
minimize earliness and quadratic tardiness penalties. Expert Systems with Applications, v. 38, p. 14490-14498.
BLUM,
C.; ROLI, A. (2003) Metaheuristics in combinatorial optimization: overview and
conceptual comparison. ACM Computing
Surveys, v. 22, n. 2, p. 241-264.
BOIKO, T. J. P.; MORAIS, M. de F. (2009). The
activity of production programming about the operational research view: a
theorical conceptual approach. In: VI ENCONTRO TECNOLÓGICO. Proceedings...
Campo Mourão: ENTEC, 2009.
BONABEAU,
E.; DORIGO, M.; THERAULAZ, G. (1999) Swarm
intelligence: from natural to artificial systems, NewYork, Oxford
University Press.
BOSCHETTI,
M. A.; MANIEZZO, V.; ROFFILLI, M.; ROHLER, A. B. (2009) Metaheuristics:
optimization, simulation and control. Lecture
Notes in Computer Science, v. 5818.
BOZORGIRAD,
M. A.; LOGENDRAN, R. (2013) Bi-criteria group scheduling in hybrid flowshops. International Journal of Production
Economics, v. 145, p. 599–612.
BURTSEVA, L.; YAURIMA, V.; PARRA, R. R. (2010) Scheduling methods for
hybrid flow shops with setup times. In: Handbook Future Manufacturing Systems. InTech.
CARVALHO,
J. D. A. (2000) Production programming. Notes.
Sistems and Production department, Engineering School from Minho University.
Available in http://pessoais.dps.uminho.pt/jdac/apontamentos/Cap03_Program.pdf.
CHO, H-M.; BAE, S-J., KIM, J.; JEONG, I-J. (2011) Bi-objective scheduling for reentrant
hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering, v. 61, p. 529-541.
DAVOUDPOUR,
H.; ASHRAFI, M. (2009) Solving multi-objective SDST flexible flow shop using
GRASP algorithm. International Journal Advanced Manufacturing Technology, v. 44,
p.737–74.
DREO,
J.; AUMASSON,J-P.; TFAILI, W.; SIARRY, P. (2007) Adaptive learning search, a new
tool to help comprehending metaheuristics. International
Journal on Artificial Intelligence Tools, v. 16. n. 3, p. 483-505.
DUGARDIN, F.; YALAOUI, F.; AMODEO, L. (2010) New
multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research,
v. 203, p. 22-31.
EBRAHIMINY,
S.M.T.; FATEMI GHOMI, S.M.T.; KARIMI, B. (2013) Hybrid flow shop scheduling
with sequence dependent family setup time and uncertain due dates. Applied Mathematical Modelling, v. 38,
n. 09-10, p. 2490-2504.
FADAEI,
M.; ZANDIEH, M. (2013) Scheduling a bi-objective hybrid flow shop with
sequence-dependent family setup times using metaheuristics. Arabian Journal of Science Engineering, v. 38, p. 2233-2244.
FAHKRZAD,
M. B.; HEYDARI, M. (2008). A heursitc algorithm for hybrid flow-shop production
scheduling to miminize the sum of the earliness and tardiness cost. Journal of the Chinese Institute of
Industrial Engineers, v. 25, n. 2, p. 105-115.
FRENCH. S. (1982).
Sequencing and scheduling: an introduction
to the mathematics of the job shop. New
York: Wiley.
GLOVER, F.; KOCHENBERGER, G. A. (2003) Handbook of Metaheuristics. Kluwer
Academic Publishers, Boston.
GODINHO FILHO, M.; MORAIS, M. F.; BOIKO, T. J. P.;
MIYATA, H. H.; VAROLO, F. W. R. (2013). Scheduling in flow shop with
sequence-dependent setup times: literature review and analysis. International Journal of Business
Innovation and Research, v. 7, n. 4, p. 466-486.
GUPTA, J. N. D.; KRUGER, K.; LAUFF, V.; WERNER, F.;
SOTSKOV, Y. N. (2002) Heuristics for hybrid flow shops with controllable
processing times and assignable due dates. Computers
& Operations Research, v. 29, p. 1417-1439.
HAN,
Z.; SHI, H.; YUAN, W.; ZHANG, Z. (2012)
Hybrid PSO/DE solution for the earliness/tardiness case of hybrid flow-shop
scheduling problem. In: INTERNATIONAL CONFERE ON MODELING, IDENTIFICATION AND
CONTROL, Wuhan, Proceedings… Wuhan: ICMIC, 2012.
HAYRINEN, T.; JOHNSSON, M.; JOHTELA, T.; SMED, J.;
NEVALAINEN. O. (2000) Scheduling algorithms for computer-aided line balancing
in printed circuit board assembly. Production
Planning and Control, v. 11, n. 5, p. 497–510.
JANIAK,
A.; KOZAN, E.; LICHTENSTEIN, M.; OGUZ, C. (2007) Metaheuristic approaches to
the hybrid flow shop scheduling problem with a cost-related criterion. International Journal of Production
Economics, v. 104, p. 407-424.
JANIAK,
A.; LICHTENSTEIN, M. (2001) Comparison of some heuristic algorithms for the
flow shop problem with parallel machines to minimize the total earliness,
tardiness and waiting time, Operations
Research Proceedings, v. 2000 - 2001, p. 378-383.
JENABI, M.; GHOMI, S. M. T. F.; TORABI, S. A.; KARIMI,
B. (2007) Two hybrid meta-heuristics for
the finite horizon ELSP in flexible flow lines with unrelated parallel
machines. Applied Mathematics and
Computation, v. 186, n.1, p. 230-245.
JOHNSON S. M.; MONTGOMERY D. C. (1974) Operations Research in Production,
Planning, Scheduling and Inventory Control. New York: Wiley.
JOHNSON, S. M.
(1954) Optimal two- and three-stage production schedules with setup times
included. Naval Research Logistics Quarterly, Hoboken, v. 1, p. 61-68.
JOLAI,
F.; ASEFI, H.; RABIEE, M.; RAMEZANI, P. (2013). Bi-objective simulated
annealing approaches for no-wait two-stage flexible flow shop scheduling
problem. Scientia Iranica, v. 20,
n.03, p. 861-872.
JUNGWATTANAKI,
J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2005). An Evaluation of Sequencing Heuristics
for Flexible Flowship Scheduling Problems with Unrelated Parallel Machines and
Dual Criteria. Magdeburg: Otto
Von Guericke, Universität Magdeburg Fakultät für
Mathematik.
JUNGWATTANAKI,
J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2007) Construtive and Tabu
Search for hybrid flow shop problems with unrelated parallel machine and setup
times. International Journal of
Computational Science, v. 1, n. 2, p. 204-214.
JUNGWATTANAKI,
J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2008). Algorithms for
flexible flow shop problems with unrelated parallel machines, setup times, and
dual criteria. Introduction Journal
Advanced Manufactury Technology, v. 37, p. 354–370.
JUNGWATTANAKI,
J.; REODECHA, M.; CHAOVALITWONGSE, P.; WERNER, F. (2009) A comparison of
scheduling algorithms for flexible flow shop problems with unrelated parallel
machines, setup times, and dual criteria. Computers
& Operations Research, v. 36, n. 2, p. 358-378.
KARIMI,
N.; ZANDIEH, M.; KARAMOOZ, H. R. (2010) Bi-objective group scheduling in hybrid
flexible flowshop: a multi-phase approach. Expert
Systems with Applications, v. 37, p. 4024-4032.
KHALOULI,
S.; GHEDJATI, F.; HAMZAOUI, A. (2008). Ant Colony Optimization for solving a
bi-criteria hybrid flow shop problem. In: INTERNATIONAL CONFERENCE ON SYSTEMS,
MAN AND CYBERNETICS, Singapore. 2008. Proceedings…Singapore: IEEE/SMC 2008.
KHALOULI,
S.; GHEDJATI, F.; HAMZAOUI, A. (2010) A meta-heuristic approach to solve a JIT
scheduling problem in hybrid flow shop.
Engineering Applications of Intelligence,
v.23, p. 765-771.
LI,
L., WANG, L.; HUO, J. (2010) Hybrid flowshop scheduling with setup times for
cold treating process in Baoshan Iron & Steel Complex. In: INTERNATIONAL
CONFERENCE ON LOGISTICS SYSTEMS AND INTELLIGENT MANAGEMENT, Harbin. Proceedings…Hammamet:
IEEE/LSIM, 2011.
LI,
X.; CHEHADE, H.; YALAOUI, F.; AMODEO, L. (2011) Lorenz dominance based metaheuristic
to solve a hybrid flowshop scheduling problem with sequence dependent setup
times. In: INTERNATIONAL CONFERENCE ON COMPUTATION AND CONTROL APPLICATIONS,
Hammamet. Proceedings…
Hammamet: CCCA, 2011.
LIN, H. T.; LIAO,
C. J. (2003) A case study in a two-stage hybrid flow shop with setup time and
dedicated machines. International
Journal of Production Economics, v. 86, n. 2, p. 133–43.
LIU,
C.; CHANG, S. (2000) Scheduling flexible flow shops with sequence-dependent
setup effect. Transactions on Robotics
and Automation, v. 16, p. 408-419.
MACCARTHY,
B. L.; LIU, J. Y. (1993). Adressing the gap in scheduling research: a review of
optimization and heuristic methods in production scheduling. International
Journal of Production Research,
v. 31, n. 1, p. 59-79.
MAHDAVI, I.; MOJARAD, M.S.; JAVADI, B.; TAJDIN, A.
(2008) A genetic approach for solving a
hybrid flow shop scheduling problem. In: INDUSTRIAL ENGINEERING AND
ENGINEERING MANAGEMENT, Singapore. Procedings…
Singapore: IEEM, 2008.
MORAIS,
M. F. (2008) Constructive heuristic methods to reduce the stock being processed
in hybrid flow shop production environments wirth setup times dependent from
sequency. Dissertation (Master’s degree)
graduation in Production Engeneering, Engeneering school from São Carlos, São
Paulo university, São Carlos.
MORAIS,
M. F.; GODINHO FILHO, M.; BOIKO, T. J. P. (2013) Hybrid flow shop scheduling
problems involving setup considerations: a literature review and analysis. International Journal of Industrial Engineering, v.
20, n.11-12, p. 613-629.
MORAIS,
M. F.; MOCCELLIN, J. V. (2010) Constructive heuristics methods to minimizing
work in process in environment production hybrid flow shop with asymmetric
sequence dependent setup times. Journal
of Management and Production, v. 17, n. 2, p. 367- 375.
MORTON,
T. E.; PENTICO, D. W. (1993) Heuristic Scheduling Systems. Wiley, New York.
MOUSAVI,
S.; ZANDIEH, M.; AMIRI, M. (2011) An efficient bi-objective heuristic for
scheduling of hybrid flow shops. The
International Journal of Advanced Manufacturing Technology, v. 54, n. 1-4,
p. 287-307.
NADERI,
B.; ZANDIEH, M.; BALAG, A.K.G.; ROSHANAEI, V.
(2009) An improved simulated annealing for hybrid flowshops with
sequence-dependent setup and transportation times to minimize total completion
time and total tardiness. Expert systems with Applications, v.36,
n.6, p. 9625-9633.
NADERI,
B.; ZANDIEH, M.; ROSHANAEI, V. (2009) Scheduling hybrid flowshops with sequence
dependent setup times to minimize makespan and maximum tardiness. International Journal Advanced
Manufacturing Technology, v. 41, p.1186–1198.
NAGAR,
A.; HADDOCK, J.; HERAGU, S. (1995) Multiple and bicritério scheduling: a
literature survey. European Journal
of Operational Research, v. 81, p.88-104.
OLIVEIRA, R. B.
(2008) Development of a multi-agent architecture based on
methaheuristics with an adaptive learning search approach. Dissertation (master’s degree). Graduation in Computational and
mathematical modeling, Federal Center of Technological Education, Minas Gerais,
Belo Horizonte.
PEREIRA,
A. M. S. (2011) Metaheuristics for the flowshop flexible with advance and
tardiness problem. Dissertation
(Master’s degree) graduation in computational science, Federal University
from Viçosa, Viçosa.
PINEDO, M.
(2008) Theory, Algorithms and Systems.
New Jersey: Prentice-Hall.
QUADT,
D.; KUHN, H. (2005) Conceptual framework for lot-sizing and scheduling of
flexible flowlines. International
Journal of Production Research, v. 43, n. 11, p. 2291–308.
QUADT,
D.; KUHN, H. (2007) Batch scheduling of jobs with identical process times on
flexible flowlines. International
Journal of Production Economics, v. 105, n. 2, p.
385–401.
RASHIDI,
E.; JAHANDAR, M.; ZANDIEH, M. (2010) An improved hybrid multi-objective parallel
genetic algorithm for hybrid flow shop scheduling with unrelated parallel
machines. International journal advanced manufacturing technology, v. 49, n.
9-12, p. 1129-1139.
RUIZ-VANOYE,
J.; DÍAZ-PARRA, O.; COCÓN, F.; SOTO, A. (2012) Meta-heuristics algorithms based
on the grouping of animals by social behavior for the traveling salesman
problem. International Journal of
Combinatorial Optimization Problems and Informatics, v. 3, n. 3, p.104-123.
SANG,
H-Y. (2013) Erratum to ‘‘A discrete colonial competitive algorithm for hybrid
flowshop scheduling to minimize earliness and quadric tardiness
penalties’’[Expert Syst. Appl. 38 (2011) 14490–14498]. Expert Systems
with Applications, v. 40, p.
4270-4272.
SAWIK, T. (2005) Integer programming approach to
production scheduling for make-to-order manufacturing. Mathematical and Computer Modelling, v. 41, n. 1, p. 99–118.
SAWIK, T. (2007) A lexicographic approach to
bi-objective scheduling of single-period orders in make-to-order manufacturing.
European Journal
of Operational Research, v.180, p.1060–1075.
SERAPIÃO, A. B. S. (2009) Optimization fundamentals by
swarm inteligence: a global view Contrlole & Automação journal, v. 20, n.
3, p.271-304.
SETHANAN, K. (2001) Scheduling flexible flowshops with
sequence dependent setup times. These
(Doctored). College of Engineering
and Mineral Resources, West Virginia
University, Morgantown.
SIMON, D. (2013) Evolutionary
optimization algorithms: biologically inspired and population-based approaches
to computer intelligence. New York: John Wiley & Sons, Inc.
SOUZA, A. B. D.;
MOCCELLIN, J. V. (2000) Hybrid metaheuristic genetic algorithm Busca-Tabu for
flow shop operations programming.In: SIMPÓSIO BRASILEIRO DE PESQUISA
OPERACIONAL, XXXII, Rio de Janeiro, Proceedings… Rio de Janeiro: SBPO, 2000.
TANG,
L.; LUH, P. B.; LIU, J.; FANG, L. (2002) Steel-making process scheduling using
Lagrangian relaxation. International
Journal of Production Research, v. 40, n. 1, p. 55-70.
TAVAKKOLI-MOGHADDAM,
R.; RAHIMI-VAHED, A.;
MIRZAEI, A. (2007) A hybrid multi-objective immune algorithm
for a flow shop scheduling problem with bi-objectives: Weighted mean completion
time and weighted mean tardiness. Information
Sciences, v. 177, p. 5072–5090.
TORABI, S. A.; FATEMI-GHOMI, S. M. T.; KARIMI, B.
(2006) A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling
in supply chains. European Journal of
Operational Research, v. 173, p.173–189.
WENG,
W.; FUJIMURA, S. (2009a) Online Scheduling of Flexible Flow Shop Manufacturing.
In: INTERNATIONAL JOINT CONFERENCE ON COMPUTATIONAL SCIENCES AND OPTIMIZATION,
Sanya, Hainan, China. Proceedings… Sanya, Hainan, China.: IJCCSO, 2009. 978-0-7695-3605-7/09.
WENG,
W.; FUJIMURA, S. (2009b) Distributed Feedback Mechanism for Just-In-Time
Scheduling Problem. IN: INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION
SCIENCE, 8, Shanghai,
China. Proceedings… Shanghai, China:
Eigth IEEE/ACIS, 2009.
WENG,
W.; WEI, X.; FUJIMURA, S. (2012) Dynamic routing strategies for JIT production
in hybrid flow shops. Computers &
Operations Research, v. 39, p. 3316-3324.
XUAN,
H; TANG, L. X. (2007) Scheduling a hybrid flow shop with batch production at
the last stage. Computers &
Operations Research, v. 34, n. 9, p. 2718–33.
YANG,
W.; LIAO, C. (1999) Survey of scheduling research involving setup times. International Journal of Systems
Science, Abington, v. 30, n. 2, p. 143-155.
YENISEY,
M. M.; YAGMAHAN, B. (2014) Multi-objective permutation flow shop scheduling
problem: Literature review, classification and current trends. Omega, v. 45, p. 119-135.
ZANDIEH,
M.; KARIMI, N. (2011) An adaptive multi-population genetic algorithm to solve
the multi-objective group scheduling problem in hybrid flexible flowshop with
sequence-dependent setup times. Journal of
Intelligence Manufacturing, v. 22, p. 979-989.