Jit Scheduling Problem on Flexible Flow Shop with Machine Break Down, Machine Eligibility and Setup Times

Volume 16, Issue 1, pp 50-68 http://dx.doi.org/10.22436/jmcs.016.01.06

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 3048 Downloads
• 4610 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

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.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [2] T. S. Arthanari, K. G. Ramamurthy, An extension of two machines sequencing problem, Operation search, 8 (1971), 10-22.
  • MathSciNet


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [7] A. Bellanger, S. Hanafi, C. Wilbaut, Three-stage hybrid- flowshop model for cross-docking, Computers & Operations Research, 40 (2013), 1109-1121.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar
  • MATH


• [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.
  • Google Scholar


• [17] Y. Honghong, W. Zhiming, The application of Adaptive Genetic Algorithms in FMS dynamic rescheduling, International Journal of Computer Integrated Manufacturing, 16 (2003), 382.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar
  • MATH


• [24] R. Logendran, S. Carson, E. Hanson, Group scheduling in flexible flowshops, International Journal of Production Economics, 96 (2005), 143-155.
  • View Article
  • Google Scholar


• [25] O. Moursli, Y. Pochet, A branch-and-bound algorithm for the hybrid flowshop, International Journal of Production Economics , 64 (2000), 113-125.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar


• [29] C. R. Reeves, Genetic algorithms for the operations researcher, INFORMS Journal on Computing, 9 (1997), 231-250.
  • View Article
  • Google Scholar
  • MATH


• [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.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar


• [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.
  • Google Scholar


• [33] L. Su, A hybrid two-stage flowshop with limited waiting time constraints, Computers & Industrial Engineering, 44 (2003), 409-424.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar
  • MATH


• [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.
  • View Article
  • Google Scholar


• [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.
  • View Article
  • Google Scholar
  • MATH


• [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.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [39] Y. Yang, S. Kreipl, M. Pinedo, Heuristics for minimizing total weighted tardiness in flexible flowshop, Journal of Scheduling, 3 (2000), 71-88.
  • Google Scholar


• [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.
  • View Article
  • Google Scholar


• [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
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH