CFP last date
21 October 2024
Reseach Article

A Novel Imperialist Competitive Algorithm to Solve Flexible Flow Shop Scheduling Problem in Order to Minimize Maximum Completion Time

by S.F.Attar, M.Mohammadi, R.Tavakkoli-Moghaddam
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 28 - Number 10
Year of Publication: 2011
Authors: S.F.Attar, M.Mohammadi, R.Tavakkoli-Moghaddam
10.5120/3426-4781

S.F.Attar, M.Mohammadi, R.Tavakkoli-Moghaddam . A Novel Imperialist Competitive Algorithm to Solve Flexible Flow Shop Scheduling Problem in Order to Minimize Maximum Completion Time. International Journal of Computer Applications. 28, 10 ( August 2011), 27-32. DOI=10.5120/3426-4781

@article{ 10.5120/3426-4781,
author = { S.F.Attar, M.Mohammadi, R.Tavakkoli-Moghaddam },
title = { A Novel Imperialist Competitive Algorithm to Solve Flexible Flow Shop Scheduling Problem in Order to Minimize Maximum Completion Time },
journal = { International Journal of Computer Applications },
issue_date = { August 2011 },
volume = { 28 },
number = { 10 },
month = { August },
year = { 2011 },
issn = { 0975-8887 },
pages = { 27-32 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume28/number10/3426-4781/ },
doi = { 10.5120/3426-4781 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:14:26.857746+05:30
%A S.F.Attar
%A M.Mohammadi
%A R.Tavakkoli-Moghaddam
%T A Novel Imperialist Competitive Algorithm to Solve Flexible Flow Shop Scheduling Problem in Order to Minimize Maximum Completion Time
%J International Journal of Computer Applications
%@ 0975-8887
%V 28
%N 10
%P 27-32
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper demonstrates solving the flexible flow shop scheduling problem (FFSP) with considering limited waiting time constraint, sequence dependent setup times and different ready time to minimize maximum completion time (i.e. makespan). Since the problem studied is NP-hard, metaheuristic algorithms are proper to solve this class of problems. Hence, in this paper, a novel imperialist competitive algorithm (ICA) is proposed to tackle of addressed problem. In order to achieve the reliable results in our proposed algorithm, a comprehensive tuning is performed using Taguchi method. to validate this proposed algorithm, the other popular algorithm namely simulated annealing is developed for this goal. Simulation results indicated that ICA is superior to SA.

References
  1. Lee GC, Kim YD. 2004. A brach-and-bound algorithm for a two-stage hybrid flow shop scheduling problem minimizing total tardiness. International Journal of Production Research, 42, 4731–43.
  2. Arthanary, T.S. and Ramamurthy, K.G. 1971. An extension of two machines sequencing problem, Opsearch, 8, 10–22.
  3. Salvador, M.S. 1973. A solution to a special case of flowshop scheduling problems", in: S.E. Elmaghraby (ed.), Symposium of the Theory of Scheduling and Applications, Springer-Verlag, New York, 83-91.
  4. Brah, S.A. 1988. Scheduling in a flow shop with multiple processors", Unpublished Ph.D. Dissertation, University of Houston, Houston, TX.
  5. Botta-Genoulaz, V. 2000. Hybrid flow shop scheduling with precedence constrains and time legs to minimize maximum lateness. International Journal of Production Economics, 64, 101–111.
  6. Kochhar, S., Morris, R. and Wong, W. 1988. The local search approach to flexible flow line scheduling. Engineering Costs and Production Economics,14(1):25–37.
  7. Wittrock, R. J. 1988. An adaptable scheduling algorithm for flexible flow lines. Journal of Operational Research, 36, 445–453.
  8. Brah, S.A. and Hunsucker, J.L. 1991. Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research, 51, 88–99.
  9. Rajendran, C. and Chaudhuri, D. 1992. Scheduling in n-job, m-stage flowshop with parallel processors to minimize makespan. International Journal of Production Economics, 27, 137–143.
  10. Vignier, A., Dardilrac, D., Dezalay, D., and Proust, C. 1996. A branch and bound approach to minimize the total completion time in a k-stage hybrid flow shop. Proceedings of the 1996 IEEE conference on emerging technologies and factory automation. (Vol. 1) (pp. 215–220).
  11. Moursli, O. and Pochet, Y. 2000. A branch-and-bound algorithm for the hybrid flow shop. International Journal of Production Economics, 64,113–125.
  12. Og˘uz, C., Ercan, M., Edwin Cheng, T. C., and Fung, Y. F. 2003. Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research, 149, 390–403.
  13. Gupta, J. N. D., Hariri, A. M. A., and Potts, C. N. 1997. Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Annals of Operations Research, 69, 171–191.
  14. Ruiz, R. and Maroto, C. 2006. A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169(3):781–800.
  15. Azizoglu, M., Cakmak, E. and Kondakci, S. 2001. A flexible flowshop problem with total flow time minimization. European Journal of Operational Research, 132,528–538.
  16. Kurz, M. E., & Askin, R. G. (2004). Scheduling flexible flow lines with sequence- dependent setup times. European Journal of Operational Research, 159, 66–82.
  17. Zandieh, M., Fatemi Ghomi, S. M. T., and Moattar Husseini, S. M. 2006. An immune algorithm approach to hybrid flowshops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180, 111–127.
  18. Jolai, F., Sheykh, S., Torabi, A. and Karimi, B. 2009. A genetic algorithm for solving no-wait flexible flow lines with due window and job rejection. International Journal of Advanced Manufacturing Technology, 42,523–532.
  19. Aldowaisan, T. andAllahverdi, A. 2004. A New heuristics for m-machine no-wait flowshop to minimize total completion time. Omega, 32, 345–352.
  20. Ruiz, R. and Allahverdi, A., 2009. New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness. International Journal of Production Research 47(20), 5717-5738.
  21. Sawik, T. 2000. Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers. Mathematical and Computer Modeling, 31(13), 39–52.
  22. Su, L-H. 2003. A hybrid two-stage flow-shop with limited waiting time constraints. Computers and Industrial Engineer, 44, 409–424.
  23. 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, doi:10.1016/j.eswa.2011.04.241
  24. Atashpaz-Gargari and Lucas, E.C. 2007. Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialist competitive. IEEE Congress on Evolutionary computation, Singapore.
  25. Bagher, M. Zandieh, M. Farsijani, H. 2010. Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm. International Journal of Advanced Manufacturing Technology. DOI 10.1007/s00170-010-2937-3
  26. Forouharfard, S. Zandieh, M., 2010. An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems. International Journal of Advanced Manufacturing Technology, 51:1179–1193.
  27. Ross, R.J., Taguchi Techniques for Quality Engineering, McGraw-Hill, USA, 1989.
  28. Phadke, M.S., Quality Engineering Using Robust Design, Prentice-Hall, USA, 1989.
  29. Al-Aomar, R., 2006. Incorporating robustness into genetic algorithm search of stochastic simulation outputs, Simulation Modeling Practice and Theory 14 , 201–223.
Index Terms

Computer Science
Information Sciences

Keywords

ICA Flexible flow shop Limited waiting time Sequence dependent setup times Ready time