Jit Scheduling Problem on Flexible Flow Shop with Machine Break Down, Machine Eligibility and Setup Times
-
3397
Downloads
-
5366
Views
Authors
N. Kangarloo
- Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran.
J. Rezaeian
- Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran.
X. Khosrawi
- Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran.
Abstract
In this research, the problem of scheduling
flexible
flowshop system with machine breakdown,
machine eligibility, machine-dependent setup time and sequence-dependent setup time to minimizing
total weighted earliness and tardiness is studied. Firstly, the problem is formulated as a Mixed
Integer Linear Programming model. With this mathematic model, small-sized instances are solved
to optimality. The considered problem is too dificult to be optimally solved for large problem sizes,
and hence two metaheuristics algorithms namely genetic algorithm (GA) and imperialist competitive
algorithm (ICA) are proposed to afford large-sized instances. Due to the sensitivity of the proposed
algorithms to parameter's values, the taguchi method as an optimization technique to widespread
tune different parameters of applied algorithms is employed to improve solutions authenticity. These
proposed algorithms were coded and tested on randomly generated examples, then to accredit the
effectiveness of them computational results are examined in terms of relative percentage deviation.
Moreover, some sensitive analyses are executed for comparing the performance of algorithms in
various conditions. The computational evaluations expressly confirm the high performance of the
proposed genetic algorithm against imperialist competitive algorithm for related scheduling problem.
Share and Cite
ISRP Style
N. Kangarloo, J. Rezaeian, X. Khosrawi, Jit Scheduling Problem on Flexible Flow Shop with Machine Break Down, Machine Eligibility and Setup Times, Journal of Mathematics and Computer Science, 16 (2016), no. 1, 50-68
AMA Style
Kangarloo N., Rezaeian J., Khosrawi X., Jit Scheduling Problem on Flexible Flow Shop with Machine Break Down, Machine Eligibility and Setup Times. J Math Comput SCI-JM. (2016); 16(1):50-68
Chicago/Turabian Style
Kangarloo, N., Rezaeian, J., Khosrawi, X.. "Jit Scheduling Problem on Flexible Flow Shop with Machine Break Down, Machine Eligibility and Setup Times." Journal of Mathematics and Computer Science, 16, no. 1 (2016): 50-68
Keywords
- mixed integer linear programming
- genetic algorithm
- imperialist competitive algorithm
- Flexible flowshop
- taguchi.
References
-
[1]
A. Allahverdi, T. C. Ng, T. C. E. Cheng, M. Y. Kovalyov, A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187 (2008), 985-1032.
-
[2]
T. S. Arthanari, K. G. Ramamurthy, An extension of two machines sequencing problem, Operation search, 8 (1971), 10-22.
-
[3]
E. Atashpaz Gargari, C. Lucas, Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition, IEEE Congress on Evolutionary Computation, Singapore, (2007), 4661-4667.
-
[4]
J. Behnamian, S. M. T. Fatemi Ghomi, Hybrid flowshop scheduling with machine and resource-dependent processing times, Applied Mathematical Modeling, 35 (2011), 1107-1123.
-
[5]
J. Behnamian, S. M. T. Fatemi Ghomi, M. Zandieh, 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, 36 (2009), 11057-11069.
-
[6]
J. Behnamian, S. M. T. Fatemi Ghomi, M. Zandieh, Development of a hybrid metaheuristic to minimize earliness and tardiness in a hybrid flowshop with sequence-dependent setup times, International Journal of Production Research, 48 (2010), 1415-1438.
-
[7]
A. Bellanger, S. Hanafi, C. Wilbaut, Three-stage hybrid- flowshop model for cross-docking, Computers & Operations Research, 40 (2013), 1109-1121.
-
[8]
V. Botta-Genoulaz, Hybrid flowshop scheduling with precedence constraints and time lags to minimize maximum lateness, International Journal of Production Economics, 64 (2000), 101-111.
-
[9]
H. S. Choi, J. S. Kim, D. H. Lee, Real-time Scheduling for Reentrant Hybrid Flow Shops: a Decision Tree Based Mechanism and Its Application to a TFT-LCD Line, Expert Systems with Applications, 38 (2011), 3514-3521.
-
[10]
O. Engin, A. Döyen, A new approach to solve hybrid flowshop scheduling problems by artificial immune systemv, Future Generation Computer Systems, 20 (2004), 1083-1095.
-
[11]
E. Figielska, A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources, Computers & Industrial Engineering, 56 (2009), 142-151.
-
[12]
E. Figielska, A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages, European Journal of Operational Research, 236 (2014), 433-444.
-
[13]
M. Gholami, M. Zandieh, An immune algorithm for scheduling a hybrid flowshop with sequence- dependent setup times and machines with random breakdowns, International Journal of Production Research, 47 (2009), 6999-7027.
-
[14]
D. E. Goldberg , Genetic algorithms in search, optimization, and machine learning, Reading, MA: Addison-Wesley (1989)
-
[15]
J. N. D. Gupta, K. Krüger, V. Lauff, F. Werner, Y. N. Sotskov, Heuristics for hybrid flow shops with controllable processing times and assignable due dates, Computers & Operations Research. , 29 (2002), 1417-1439.
-
[16]
M. Heydari, E. Mohammadi, A fuzzy heuristic algorithm for the flow shop scheduling problem, The Journal of Mathematics and Computer Science, 4 (2010), 349-354.
-
[17]
Y. Honghong, W. Zhiming, The application of Adaptive Genetic Algorithms in FMS dynamic rescheduling, International Journal of Computer Integrated Manufacturing, 16 (2003), 382.
-
[18]
A. Janiaka, E. Kozanb, M. Lichtensteina, C. Oguzc, Metaheuristic approaches to the hybrid flowshop scheduling problem with a cost-related criterion, International Journal of Production Economics, 105 (2007), 407-424.
-
[19]
Z. Jin, Z. Yang, T. Ito, Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem, International Journal of Production Economics, 100 (2006), 322-334.
-
[20]
J. Jungwattanakit, M. Reodecha, M. P. Chaovalitwongse, F. Werner, A comparison of scheduling algorithms for flexible flowshop problems with unrelated parallel machines, setup times, and dual criteria, Computer & Operation Research, 36 (2009), 358-378.
-
[21]
S. Khalouli, F. Ghedjati, A. Hamzaoui, A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop, Engineering Applications of Artificial Intelligence, 23 (2010), 765-771.
-
[22]
H. R. Kia, H. Davoudpour, M. Zandieh , Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis, International Journal of Production Research, 48 (2010), 4019-4042.
-
[23]
F. S. C. Lam, B. C. Lin, C. Sriskandarajah, H. Yan, Scheduling to minimize product design time using a genetic algorithm, International Journal of Production Research, 37 (1999), 1369-1386.
-
[24]
R. Logendran, S. Carson, E. Hanson, Group scheduling in flexible flowshops, International Journal of Production Economics, 96 (2005), 143-155.
-
[25]
O. Moursli, Y. Pochet, A branch-and-bound algorithm for the hybrid flowshop, International Journal of Production Economics , 64 (2000), 113-125.
-
[26]
A. Naderi, M. Zandieh, A. Khaleghi Ghoshe Balagh, V. Roshanaei, 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, 36 (2008), 9625-9633.
-
[27]
T. Nishi, Y. Hiranaka, M. Inuiguchi, Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness, Computers & Operations Research, 37 (2010), 189-198.
-
[28]
Q. K. Pan, L. Wang, J. Q. Li, J. H. Duan, A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimization, Omega, 45 (2014), 42-56.
-
[29]
C. R. Reeves, Genetic algorithms for the operations researcher, INFORMS Journal on Computing, 9 (1997), 231-250.
-
[30]
R. Ruiz, C. Maroto, A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility, European Journal of Operational Research, 169 (2006), 781-800.
-
[31]
M. S. Salvador, A solution to a special case of flowshop scheduling problems, In: Elmaghraby SE, editor, Symposium of the theory of scheduling and its applications, New York: Springer, (1973), 83-91.
-
[32]
H. Seidgar, M. Ezzati, M. kiani, R. Tavakoli-Moghaddam, An Efficient Genetic Algorithm for Two- stage Hybrid Flow Shop Scheduling with Preemption and Sequence Dependent Setup Time, Journal of Mathematics and Computer Science, 6 (2013), 251-259.
-
[33]
L. Su, A hybrid two-stage flowshop with limited waiting time constraints, Computers & Industrial Engineering, 44 (2003), 409-424.
-
[34]
L. Tang, W. Liu, J. Liu, A neural network model and algorithm for the hybrid flowshop scheduling problem in a dynamic environment , Journal of Intelligent Manufacturing, 16 (2005), 361-370.
-
[35]
L. Tang, H. Xuan, J. Liu, A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time, Computers & Operations Research, 33 (2006), 3344-3359.
-
[36]
S. Vob, A. Witt, Hybrid flowshop scheduling as a multi-mode multi-project scheduling problem with batching requirements, International Journal of Production Economics, 105 (2007), 445-458.
-
[37]
X. Wang, L. Tang, A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers, Computers & Operations Research, 36 (2009), 907-918.
-
[38]
J. Xie, X. Wang, Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints, Computer and Mathematics with Application, 50 (10-12) (2005), 1629-1638.
-
[39]
Y. Yang, S. Kreipl, M. Pinedo, Heuristics for minimizing total weighted tardiness in flexible flowshop, Journal of Scheduling, 3 (2000), 71-88.
-
[40]
V. Yaurima, L. Burtseva, A. Tchernykh, Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers, Computers & Industrial Engineering, 56 (2009), 1452-1463.
-
[41]
M. Zandieh, S. M. T. Fatemi Ghomi, S. M. Moattar Husseini, An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times, Journal of Applied Mathematics and Computation, 180 (2006), 111-127