No Access

USING ANT COLONY OPTIMIZATION TO MINIMIZE THE FUZZY MAKESPAN AND TOTAL WEIGHTED FUZZY COMPLETION TIME IN FLOW SHOP SCHEDULING PROBLEMS

PENG-JEN LAI

Department of Mathematics, National Kaohsiung Normal University, Kaohsiung 802, Taiwan

Search for more papers by this author

and

HSIEN-CHUNG WU

Department of Mathematics, National Kaohsiung Normal University, Kaohsiung 802, Taiwan

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218488509006145Cited by:4 (Source: Crossref)

Abstract

The flow shop scheduling problems with fuzzy processing times are investigated in this paper. For some special kinds of fuzzy numbers, the analytic formulas of the fuzzy compltion time can be obtained. For the general bell-shaped fuzzy numbers, we present a computational procedure to obtain the approximated membership function of the fuzzy completion time. We define a defuzzification function to rank the fuzzy numbers. Under this ranking concept among fuzzy numbers, we plan to minimize the fuzzy makespan and total weighted fuzzy completion time. Because the ant colony algorithm has been successfully used to solve the scheduling problems with real-valued processing times, we shall also apply the ant colony algorithm to search for the best schedules when the processing times are assumed as fuzzy numbers. Numerical examples are also provided and solved by using the commercial software MATLAB.

Keywords:

References

B. Bullnheimer, R. F. Hartl and C. Strauss, Annals of Operations Research 89, 319 (1999), DOI: 10.1023/A:1018940026670. Crossref, Web of Science, Google Scholar
B. Bullnheimer , R. F. Hartl and C. Strauss , Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization , eds. S. Voss et al. ( Kluwer , Boston , 1999 ) . Google Scholar
R. L. Burden and J. D. Faires, Numerical Analysis, 7th edn. (Brooks/Cole, 2001). Google Scholar
S. Chanas and A. Kasperski, Engineering Applications of Artificial Intelligence 14, 377 (2001), DOI: 10.1016/S0952-1976(01)00011-2. Crossref, Web of Science, Google Scholar
S. Chanas and A. Kasperski, European Journal of Operational Research 147, 281 (2003), DOI: 10.1016/S0377-2217(02)00561-1. Crossref, Web of Science, Google Scholar
J. Cheng, H. Kise and H. Matsumoto, European Journal of Operational Research 96, 578 (1997), DOI: 10.1016/S0377-2217(96)00026-4. Crossref, Web of Science, Google Scholar
D. Costa and A. Hertz, Journal of the Operational Research Society 48, 295 (1997), DOI: 10.1057/palgrave.jors.2600357. Crossref, Web of Science, Google Scholar
G. Di Caro and M. Dorigo, Journal of Artificial Intelligence Research 9, 317 (1998). Crossref, Web of Science, Google Scholar
A. V. Donatiet al., European Journal of Operational Research 185, 1174 (2008), DOI: 10.1016/j.ejor.2006.06.047. Crossref, Web of Science, Google Scholar
M. Dorigo and L. M. Gambardella, IEEE Transaction on Evolutionary Computation 1, 53 (1997), DOI: 10.1109/4235.585892. Crossref, Google Scholar
M. Dorigo and L. M. Gambardella, BioSystem 43, 73 (1997), DOI: 10.1016/S0303-2647(97)01708-5. Crossref, Web of Science, Google Scholar
M. Dorigo and T. Stützle , Ant Colony Optimization ( MIT Press , 2004 ) . Crossref, Google Scholar
K. Socha and M. Dorigo, European Journal of Operational Research 185, 1155 (2008), DOI: 10.1016/j.ejor.2006.06.046. Crossref, Web of Science, Google Scholar
Y. Gajpal and P. L. Abad, European Journal of Operational Research (2008), DOI: doi:10.1016/j.ejor.2008.02.025. Google Scholar
Gambardella, L. M. and Dorigo, M., HAS-SOP: hybrid ant system for the sequential ordering problem, Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland, 1997 . Google Scholar
L. M. Gambardella, É. Taillard and G. Agazzi, New Ideas in Optimization, eds. D. Corne, M. Dorigo and F. Glover (McGraw-Hill, 1999) pp. 63–76. Google Scholar
L. M. Gambardella, É. D. Taillard and M. Dorigo, J. Operational Research Society 50, 167 (1999). Crossref, Web of Science, Google Scholar
K. K. Harikrishnan and H. Ishii, Fuzzy Optimization and Decision Making 4, 141 (2005), DOI: 10.1007/s10700-004-5870-9. Crossref, Web of Science, Google Scholar
H. Ishibuchiet al., Int. J. Production Economics 33, 53 (1994), DOI: 10.1016/0925-5273(94)90118-X. Crossref, Web of Science, Google Scholar
H. Ishibuchiet al., Fuzzy Sets and Systems 67, 81 (1994), DOI: 10.1016/0165-0114(94)90210-0. Crossref, Web of Science, Google Scholar
H. Ishii, M. Tada and T. Masuda, Fuzzy Sets and Systems 46, 339 (1992), DOI: 10.1016/0165-0114(92)90372-B. Crossref, Web of Science, Google Scholar
T. Itoh and H. Ishii, Int. Trans. Operational Research 6, 639 (1999), DOI: 10.1111/j.1475-3995.1999.tb00178.x. Crossref, Google Scholar
T. Itoh and H. Ishii, Fuzzy Optimization and Decision Making 4, 71 (2005), DOI: 10.1007/s10700-004-5571-4. Crossref, Google Scholar
G. J. Klir and B. Yuan , Fuzzy Sets and Fuzzy Logic: Theory and Applications ( Prentice-Hall , 1995 ) . Google Scholar
P. Kuntz and D. Snyers , Emergent colonization and graph partitioning , Proc. Third Int. Conf. Simulation of Adaptive Behavior: From Animals to Animates 3 ( The MIT Press , 1994 ) . Google Scholar
P. Kuntz , P. Layzell and D. Snyers , A colony of ant-like agnets for partitioning in VLSI technology , Proc. Fourth European Conf. Artificial Life ( The MIT Press , 1994 ) . Google Scholar
J. Liu and C. R. Reeves, European J. of Operational Research 131, 439 (2001). Web of Science, Google Scholar
C. J. Liao and H. C. Juan, Computers and Operations Research 34, 1899 (2007), DOI: 10.1016/j.cor.2005.07.020. Crossref, Web of Science, Google Scholar
V. Maniezzo and A. Colorni, IEEE Trans. Knowledge and Data Engineering 11(5), 769 (1999), DOI: 10.1109/69.806935. Crossref, Web of Science, Google Scholar
T. Murata, M. Gen and H. Ishibuchi, Computers and Industrial Engineering 35, 439 (1998), DOI: 10.1016/S0360-8352(98)00128-4. Crossref, Web of Science, Google Scholar
C. V. Negoita and D. A. Ralescu , Applications of Fuzzy Sets to Systems Analysis ( Wiley , NY , 1975 ) . Crossref, Google Scholar
M. Pinedo , Scheduling: Theory, Algorithms and Systems , 2nd edn. ( Prentice Hall , NJ , 2002 ) . Google Scholar
C. Rajendran and H. Ziegler, European J. Operational Research 155, 426 (2004), DOI: 10.1016/S0377-2217(02)00908-6. Crossref, Web of Science, Google Scholar
V. Ramos and F. Almeida, Artificial ant colonies in digital image habitats-a mass behavior effect study on pattern recognition, Proc. ANTS'2000-Second Int. Workshop on Ant Algorithms pp. 113–116. Google Scholar
M. Sakawa and R. Kubota, European J. Operational Research 120, 393 (2000), DOI: 10.1016/S0377-2217(99)00094-6. Crossref, Web of Science, Google Scholar
M. Sakawa and T. Mori, Computers and Industrial Engineering 36, 325 (1999), DOI: 10.1016/S0360-8352(99)00135-7. Crossref, Web of Science, Google Scholar
R. Schoonderwoerdet al., Adaptive Behavior 5, 169 (1997), DOI: 10.1177/105971239700500203. Crossref, Web of Science, Google Scholar
S. J. Shyu, B. M. T. Lin and P. Y. Yin, Annals of Operations Research 131, 283 (2004), DOI: 10.1023/B:ANOR.0000039523.95673.33. Crossref, Web of Science, Google Scholar
R. Słowiński and M. Hapke , Scheduling under Fuzziness ( Physica-Verlag , New York , 2000 ) . Google Scholar
C. Solnon, European J. of Operational Research 191, 1043 (2008), DOI: 10.1016/j.ejor.2007.04.037. Crossref, Web of Science, Google Scholar
Y. H. Song and C. S. Chou, IEEE Power Engineering Review 18, 63 (1998). Google Scholar
I. Temiz and S. Erol, J. Intelligent Manufacturing 15, 449 (2004), DOI: 10.1023/B:JIMS.0000034107.72423.b6. Crossref, Web of Science, Google Scholar
W. Xiang and H. P. Lee, Engineering Applications of Artificial Intelligence 21, 73 (2008), DOI: 10.1016/j.engappai.2007.03.008. Crossref, Web of Science, Google Scholar
B. Yagmahan and M. M. Yenisey, Computers and Industrial Engineering 54, 411 (2008), DOI: 10.1016/j.cie.2007.08.003. Crossref, Web of Science, Google Scholar
K. C. Ying and C. J. Liao, Computers and Operations Reasearch 31, 791 (2004), DOI: 10.1016/S0305-0548(03)00038-8. Crossref, Web of Science, Google Scholar
L. A. Zadeh, Information and Control 8, 338 (1965), DOI: 10.1016/S0019-9958(65)90241-X. Crossref, Google Scholar
Zadeh, L. A., The Concept of Linguistic Variable and Its Application to Approximate Reasoning I, II and III, Information Sciences 8 (1975) 199–249; ibid. 8 (1975) 301–357 and ibid. 9 (1975) pp. 43–80 . Google Scholar
H.-J. Zimmermann , Fuzzy Sets Theory and Its Applications , 2nd edn. ( Kluwer Academic Publishers , New York , 1991 ) . Crossref, Google Scholar