Sıra bağımlı hazırlık süreli iki ölçütlü tek makine çizelgeleme problemi için sezgisel bir çözüm yöntemi
Bu çalışmada sıra bağımlı hazırlık süreli, son işin tamamlanma zamanını ve toplam gecikmeyi en aza indirmeyi amaçlayan tek makine çizelgeleme problemi ele alınmıştır. Bu problem NP-zor sınıfında yer almaktadır. Problemin çözümü için ilk olarak, SST (en kısa hazırlık süresi) sıralama kuralının ağırlıklandırılmış hali olan yeni bir sıralama kuralı (WSST) önerilmiştir. Bu sıralama kuralı, literatürde yer alan EDD (en küçük teslim zamanı), SST ve ATCS (Apparent Tardiness Cost with Setups) sıralama kurallarıyla karşılaştırılmıştır. Daha sonra, önerilen sıralama kuralının çözümlerini, bir yerel arama yöntemiyle iyileştirme amacını güden yeni bir sezgisel algoritma önerilmiştir. Önerilen yöntemlerin etkinliği rassal olarak türetilen test problemleri kullanılarak araştırılmıştır.
A heuristic for bicriteria single machine scheduling problem with sequence dependent setup times
In this study, the bi-criteria scheduling problem of minimizing the makespan and total tardiness on a single machine with sequence dependent setup times is considered. This problem is known as NP-hard. To solve this problem, firstly we propose a new dispatching rule named as WSST that is the weighted form of the SST (Shortest Setup Time) rule. The proposed rule is compared with EDD (Earliest Due Date), SST and ATCS (Apparent Tardiness Cost with Setups) dispatching rules. And then, a new heuristic which improves the solutions of the WSST by a local search algorithm is proposed. The performance of the proposed heuristics is tested by using randomly generated test problems.
___
- 1. Armentano, V.A., Mazzini, R. 2000. “A Genetic Algorithm For Scheduling On A Single Machine With Set-Up Times And Due Dates,” Production Planning and Control, 11, 713–720.
- 2. Asano, M., Ohta, H. 1999. “Scheduling With Shutdowns And Sequence Dependent Set-Up Times,” International Journal of Production Research, 37, 1661–1676.
- 3. Chang, T.Y., Chou, F.D., Lee, C.E. 2004. “A Heuristic Algorithm To Minimize Total Weighted Tardiness On A Single Machine With Release Dates And Sequence-Dependent Setup Times,” Journal of the Chinese Institute of Industrial Engineers, 21, 289–300.
- 4. Chankong, V., Haimes, Y.Y. 1983. “Multiobjective Decision Making: Theory and Methodology”, Elsevier Science Publishing Co, New York.
- 5. Choobineh, F.F., Mohebbi, E., Khoo, H. 2006. “A Multi-Objective Tabu Search For A Single-Machine Scheduling Problem With Sequence-Dependent Setup Times,” European Journal of Operational Research, 175, 318–337.
- 6. Ehrgott, M. 2005. “Multicriteria Optimization,” Springer-Verlag, 2nd edition.
- 7. Eren, T., Guner, E. 2006. “A Bicriteria Scheduling With Sequence Dependent Setup Times,” Applied Mathematics and Computation, 179, 378–385.
- 8. Franca, P.M., Mendes, A., Moscato, P. 2001. “A Memetic Algorithm For The Total Tardiness Single Machine Scheduling Problem,” European Journal of Operational Research, 132, 224–242.
- 9. Gagne, C., Price, W.L., Gravel, M. 2002. “Comparing an ACO Algorithm With Other Heuristics For The Single Machine Scheduling Problem With Sequence-Dependent Setup Times,” Journal of the Operational Research Society, 53, 895–906.
- 10. Gupta, S.R., Smith, J.S. 2006. “Algorithms For Single Machine Total Tardiness Scheduling With Sequence Dependent Setups,” European Journal of Operational Research, 175, 722–739.
- 11. Kolahan, F., Liang, M. 1998. “An adaptive TS Approach To JIT Sequencing With Variable Processing Times And Sequencedependent Setups,” European Journal of Operational Research, 109, 142–159.
- 12. Lee, S.M., Asllani, A.A. 2004. “Job Scheduling With Dual Criteria And Sequence-Dependent Setups: Mathematical Versus Genetic Programming,” Omega, 32, 145–153.
- 13. Luc, D.T. 1989. “Theory of Vector Optimization,” Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin.
- 14. Mendes, A.S., Franca, P.M., Moscato, P. 2002. “Fitness Landscapes For The Total Tardiness Single Machine Scheduling Problem,” Neural Network World, 12, 165–180.
- 15. Miller, D.M., Chen, H.C., Matson, J., Liu, Q. 1999. “A Hybrid Genetic Algorithm For The Single Machine Scheduling Problem,” Journal of Heuristics, 5, 437–454.
- 16. Pinedo, M. 2002. “Scheduling: Theory, Algorithms and Systems,” 2nd Edition, Prentice Hall.
- 17. Rabadi, G., Mollaghasemi, M., Anagnostopoulos, G.C. 2004. “A Branch-And-Bound Algorithm For The Early/ Tardy Machine Scheduling Problem With A Common Due-Date And Sequence Dependent Setup Time,” Computers and Operations Research, 31, 1727–1751.
- 18. Rajendran, C., Ziegler, H. 2003. “Scheduling to Minimize the Sum of Weighted Flowtime and Weighted Tardiness of Jobs in A Flowshop with Sequence-Dependent Setup Times,” European Journal of Operational Research, 149 (3), 513–522.
- 19. Shin, H.J., Kim, C.O., Kim, S.S. 2002. “A Tabu Search Algorithm For Single Machine Scheduling With Release Times, Due Dates, And Sequence-Dependent Set-Up Times,” International Journal of Advanced Manufacturing Technology, 19, 859–866.
- 20. Tan, K.C., Narasimhan, R. 1997. “Minimizing Tardiness On A Single Processor With Sequence-Dependent Setup Times: A Simulated Annealing Approach,” Omega, 25, 619–634.
- 21. Tan, K.C., Narasimhan, R., Rubin, P.A., Ragatz, G.L. 2000. “A Comparison Of Four Methods For Minimizing Total Tardiness On A Single Processor With Sequence Dependent Setup Times,” Omega, 28, 313–326.
- 22. Wang, L., Wang, M. 1997. “Hybrid Algorithm For Earliness–Tardiness Scheduling Problem With Sequence Dependent Setup Time,” Proceedings of the IEEE Conference on Decision and Control, 2, 1219–1222.
- ISSN: 1300-3410
- Yayın Aralığı: Yılda 3 Sayı
- Başlangıç: 1989
- Yayıncı: TMMOB MAKİNA MÜHENDİSLERİ ODASI