İKİ ÖLÇÜTLÜ TEK MAKİNALI ÇİZELGELEME PROBLEMİ İÇİN SEZGİSEL BİR YAKLAŞIM

Öz

Bu çalışmada, en küçük geciken iş kısıtı altında en büyük erken tamamlanma zamanının en küçüklendiği ikincil ölçütlü bir problem dikkate alınmıştır. Bu problem için geliştirilmiş olan dal-sınır algoritmasında çözüm zamanı, problem büyüklüğüne bağlı olarak üstel artış göstermektedir. Son yıllarda, çizelgeleme problemlerin çözümünde global en iyi çözümü bulmada başarılı olan genetik algoritmalar, tavlama benzetimi, tabu arama ve sinir ağları gibi yeni tekniklerin sıkça kullanıldığı  görülmektedir. Bu çalışmada, bu problem için tavlama benzetimi tekniğine dayalı bir algoritma geliştirilmiştir. Geliştirilen algoritmanın performansında çeşitli komşu üretim mekanizmalarının etkileri rassal üretilen test problemleri üzerinde incelenmiştir.

Anahtar Kelimeler

• Çizelgeleme, çok ölçütlü çizelgeleme, tavlama benzetimi

Kaynakça

1. Smith, W.E., “Various optimizers for single stage production”, Naval Research Logistic Quarterly, 3, 59-66, (1956).
2. Heck, H., Roberts, R., “A note on the extension of a result on scheduling with secondary criteria”, Naval Research Logistic Quarterly, 19, 403-405, (1972).
3. Burns, R. N., “Scheduling to minimize the weighted completion times with secondary criteria”, Naval Research Logistic Quarterly, 23, 125-129, (1976).
4. Miyazaki, S., “One machine scheduling problem with dual criteria”, Journal of Operations Research Society of Japan, 24 (1), 37-51, (1981).
5. Bansal, S. P., “Single machine scheduling to minimize the weighted sum of completion times with secondary criterion, a branch and bound approach”, European Journal of Operations Research, 5, 177-181, (1980).
6. Shanthikumar, J. G., Buzacott, J. A., “On the use of decomposition approaches in a single machine scheduling problem”, Journal of Operations Research Society of Japan, 25, 29-47, (1982).
7. Posner, M. E., “Minimizing weighted completion times with deadlines”, Operations Research, 33, 562-574, (1985).
8. Bagchi, U., Ahmadi, R. H., “An improved lower bound for minimizing weighted completion times with deadlines”, Operations Research, 35, 311-313, (1987).

9. Chand, S., Schneeberger, H., “A note on the single machine scheduling problem with minimum weighted completion time and maximum allowable tardiness”, Naval Research Logistic Quarterly, 33 551-557, (1986).
10. Shanthikumar, J. G., “Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number tardy”, Computers & Operations Research, 10, 255-266, (1983).
11. Gupta, J. N. D., and Ramnarayanan, “Single facility with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs”, Production Planning & Control, 7, 2, 190-196, (1996).
12. Gupta, J.N.D., Hariri, A.M.A and Potts, R., “Single-machine scheduling to minimize Maksimum Tradiness with Minimum Number of Tardy Jobs”, Annals of Operations Research, 92, 107-123, (1999).
13. Emmons, H., “One machine sequencing to minimize mean flow time with minimum number tardy”, Naval Research Logistic Quarterly, 22, 585-592, (1975).
14. Chand, S., Schneeberger, H., “Single machine scheduling to minimize weighted earliness subject to no tardy jobs”, European Journal of Operations Research, 34, 221-230, (1988).
15. Güner, E., Erol S., Tani K., “One machine scheduling to minimize the maximum earliness with minimum number tardy jobs”, International Journal of Production Economics, 55, 213-219, (1998).
16. Chang, P.C., Su, L.H., “Scheduling n Jobs on One Machine to Minimize The Maximum Lateness with a Minimum Number of Tardy Jobs”, Computers and Industrial Engineering, 40, 349-360, 2001.
17. Kirkpatrick, S., Gelatt, Jr., C. D., and Vecchi, M. P., “Optimization by simulated annealing”, Science, 220, 671-680, (1983).
18. Cerny, V., “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”, Journal of Optimization Theory and Applications, 45, 41-51, (1985).
19. Metropolis, N., Rosenbluth, A., Rosenbluth,M., Teller, A., Teller, E., “ Equation of state calculations by fast computing machines”, Journal of Chemical Physics, 21, 1087-1092, (1953).
20. Matsuo, H., Chang, J.S., Sullivan, R.S., “A controlled search simulated annealing method for the single machine weighted tardiness problem”, Annals of Operations Research, 21, 85-108, (1989).
21. Lin, C.K.Y., Haley, K.B., Sparks, C., “A comparative study of both standard and adaptive versions of threshold accepting and simulated annealing in three scheduling problems”, European Journal of Operational Research, 83, 330-346, (1995).
22. Shapiro, J. A., Alfa, A. S.,” An experimental analysis of the simulated annealing algorithm for a single machine scheduling problem”, Engineering Optimization, 24, 79-100, (1995).
23. Crauwels, H.A.J., Potts, C.N., Van Wassenhove, L.N., “Local search heuristics for single machine scheduling with batching to minimize the number of late jobs”, European Journal of Operational Research, 90, 200-213, (1996).
24. Bendaya, M., Al-Fawzan, M., “Simulated annealing approach for the one machine mean tardiness scheduling problem”, European Journal of Operational Research, 93(1), 61-67, (1996).
25. Guinet, A., “Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria”, Journal of Intelligent Manufacturing, 6(2), 95-103, (1995).
26. Osman, I. H., and Potts C.N., “Simulated annealing for permutation flowshop scheduling,” OMEGA, International Journal of Mgmt Sci., 17(6), 551-557, (1989).
27. Ogbu, F. A., Smith, D.K., “Simulated annealing for the permutation flowshop problem”, OMEGA, 19, 1, 64-67, (1990a).
28. Ogbu, F. A., Smith, D.K., “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flow shop problem”, Computers & Operations Research, 17(3), 243-253, (1990b).
29. Zegardi, S.H., Itah, K., Enkawa, T., “Minimizing makespan for flowshop scheduling by combining simulated annealing with sequencing knowledge”, European Journal of Operational Research, 85(3), 515-531, (1995a).
30. Ishibuchi H., Misaki, S., Tanaka, H., “Theory and Methodology modified simulated annealing algorithms for the flow shop sequence problem”, European Journal of Operations Research, 81, 388-398, (1995).
31. Parthasarathy, S., Rajendran, C.,” A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs- a case study”, Production Planning & Control, 8(5), 475-483, (1997).
32. Van Laarhoven, P.J.M., Aarts, E. H. L., Lenstra, J. K.,” Job shop scheduling by simulated annealing”, Operations Research, 40, 113-125, (1992).
33. Krishna, K., Ganeshan, K., Ram, D.J., “Distributed simulated annealing algorithms for jobshop scheduling”, IEEE Transactions on Systems, Man and Cybernetics, 25(7), 1102-1109, (1995).
34. Mamalis, A.G., Malagandis, I., “Determination of due dates in job shop scheduling by simulated annealing”, Computer Integrated Manufacturing Systems, 9(2), 65-72, (1996).
35. Catoni, O., “Solving scheduling problems by simulated annealing”, SIAM Journal on Control and Optimization, 36(5), 1539-1575, (1998).
36. Gangadharan, R.G., Rajendran, C., “A simulated annealing heuristics for scheduling in a flow shop with bicriteria”, Computers & Industrial Engineering, 27(1-4), 473-476, (1994).
37. Park, M.W., Kim, Y.D., “Search heuristics for a parallel machine scheduling problem with ready times and due sates”, Computers & Industrial Engineering, 33(3-4), 793-796, (1997).
38. Ruiz- Torres, A., Enscore, E. E., Barton, R. R., “Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problen”, Computers & Industrial Engineering, 33 (1-2), 257-260, (1997).
39. Lee, S. S., Wang, H-P.B., “Modified simulated annealing for multiple-objective engineering design optimization”, Journal of Intelligent Manufacturing, 3, 101-108, (1992).
40. Lundy, M., and Mees, A., “Convergence of an annealing algorithm”, Mathematical Programming, 34, 111-124 (1986).
41. Fisher, M.L.,”A dual algorithm for the one-machine scheduling problem”, Mathematical Programming, 11,229- 251 (1976).