PARALEL MAKİNELERDE İŞLERİN VE MAKİNE OPERATÖRLERİNİN BİRLİKTE ÇİZELGELENMESİ PROBLEMİNE ÇÖZÜM YAKLAŞIMLARI

Year 2012, Volume: 27 Issue: 3, 0 - , 19.02.2013

Emralı B. Edis Ceyda Oğuz İrem Özkarahan

Abstract

Literatürde ele alınan paralel makine çizelgeleme problemlerinin çoğunluğu, işlerin ihtiyaç duyduğu tekkaynağın makine olduğu varsayımına dayanır ve yalnızca iş-makine çizelgeleme problemi ile ilgilenir. Oysagerçek yaşam problemlerinde işler, makineler dışındaki ek kaynaklara da gereksinim duymaktadır. Ekkaynakların en çok karşılaşılan örneği, farklı makinelerde farklı işlerle çalışabilme yeteneğine sahip olan makineoperatörleridir. Bu çalışmada işlerin ve operatörlerin paralel makineler boyunca çizelgelenmesini gerektiren birgerçek yaşam problemi ele alınmıştır. Operatörler, makineleri izlemek, ürünleri çıkarmak, ürün üzerindekifazlalıkları almak vb. işlemlerle sorumludur. Bu işlemler, herhangi bir ürünün işlenme süresinin tamamı boyuncabir operatörün makine başında durmasını gerektirmeyebilir. Bu kapsamda, ele alınan problemin yazındaki benzerçalışmalardan önemli bir farkı; bir operatörün belli zaman dilimleri boyunca birden fazla makineye atanabilmesiözelliğidir. Operatörün aynı zaman diliminde ilgileneceği makineler belirlenirken, makinelerin fizikselyakınlıkları da dikkate alınmalıdır. Ele alınan problem için en son işin bitiş süresini en küçükleme amaçlıtamsayı ve kısıt programlama modelleri geliştirilmiştir. Geliştirilen modeller, farklı parametreler içeren testproblemlerine uygulanmış ve performansları değerlendirilmiştir. Son olarak, kısıt programlama modeliningerçek yaşam problemine uygulanabilirliği gösterilmiştir.

Keywords

paralel makineler, iş ve operatör çizelgeleme, tamsayı programlama, kısıt programlama

References

• Pinedo M., Scheduling: Theory, Algorithms,
• and Systems, 2. basım, Prentice-Hall,
• Englewood-Cliffs, NJ, A.B.D., 2002.
• Ventura, J.A. ve Kim, D., “Parallel machine
• scheduling with earliness-tardiness penalties and
• additional resource constraints”, Computers &
• Operations Research, Cilt 30, 1945–1958, 2003.
• Daniels, R.L., Hua, S.Y., ve Webster, S.,
• “Heuristics for Parallel-Machine Flexible-
• Resource Scheduling Problems with Unspecified
• Job Assignment”, Computers & Operations
• Research, Cilt 26, 143-155, 1999.
• Edis, E.B., Oğuz, C. ve Özkarahan, İ., “Paralel
• Makinelerde İşlerin ve Makine Operatörlerinin
• Birlikte Çizelgelenmesi Problemine Çözüm
• Yaklaşımları”, Yöneylem Araştırması ve
• Endüstri Mühendisliği 30. Ulusal Kongresi
• Bildiri Özetleri Kitabı, Sabancı Üniversitesi,
• İstanbul, 338, 30 Haziran-2 Temmuz 2010.
• Edis, E.B., “Resource Constrained Parallel
• Machine Scheduling Problems with Machine
• Eligibility Restrictions: Mathematical and
• Constraint Programming Based Approaches”,
• Doktora Tezi, Dokuz Eylül Üniversitesi, Fen
• Bilimleri Enstitüsü, Ocak 2010.
• Daniels, R.L., Hoopes, B.J. ve Mazzola J.B.,
• “Scheduling Parallel Manufacturing Cells with
• Resource Flexibility”, Management Science,
• Cilt 42, No 9, 1260-1276, 1996.
• Chen, Z., “Simultaneous Job Scheduling and
• Resource Allocation on Parallel Machines”,
• Annals of Operations Research, Cilt 129, 135–
• , 1999.
• Grigoriev, A., Sviridenko, M. ve Uetz, M., “LP
• rounding and an almost harmonic algorithm for
• scheduling with resource dependent processing
• times”, Lecture Notes in Computer Science,
• Cilt 4110, Editörler: Diaz, J., Jansen, K., Rolim,
• J. ve Zwick, U., Springer-Verlag, Berlin,
• Almanya, 140-151, 2006.
• Grigoriev, A., Sviridenko, M. ve Uetz, M.,
• “Machine scheduling with resource dependent
• processing times”, Mathematical Programming
• Series B, Cilt 110, 209-228, 2007.
• Grigoriev, A., Sviridenko, M. ve Uetz, M.,
• “Unrelated parallel machine scheduling with
• resource dependent processing times”, Lecture
• Notes in Computer Science, Cilt 3509,
• Editörler: Jünger, M. ve Kaibel V., Springer-
• Verlag, Berlin, Almanya, 182-195, 2005.
• Hu, P.C., “Minimising Total Tardiness for the
• Worker Assignment Scheduling Problem in
• Identical Parallel-Machine Models”,
• International Journal of Advanced
• Manufacturing Technology, Cilt 23, No 5–6,
• –388, 2004.
• Hu, P.C., “Minimizing Total Flow Time for the
• Worker Assignment Scheduling Problem in the
• Identical Parallel-Machine Models”,
• International Journal of Advanced
• Manufacturing Technology, Cilt 25, No 9–10,
• –1052, 2005.
• Chaudry, I.A. ve Drake, P.R., “Minimizing total
• tardiness for the machine scheduling and worker
• assignment problems in identical paralel
• machines using genetic algorithms”,
• International Journal of Advanced
• Manufacturing Technology, Cilt 42, 581–594,
• -
• Chaudry, I.A., “Minimizing flow time for the
• worker assignment problem in identical parallel
• machine models using GA”, International
• Journal of Advanced Manufacturing
• Technology, Cilt 48, 747–760, 2010.
• Edis, E.B, Araz, C. ve Ozkarahan, I.
• "Lagrangian-Based Solution Approaches for a
• Resource-Constrained Parallel Machine
• Scheduling Problem with Machine Eligibility
• Restrictions", Lecture Notes in Computer
• Science, Cilt 5027, Editörler: Nguyen, N.T. vd.,
• Springer-Verlag, Berlin, Almanya, 337-346,
• -
• Edis, E. B. ve Ozkarahan, I. “A combined
• integer/constraint programming approach to a
• resource-constrained parallel machine scheduling
• problem with machine eligibility restrictions”,
• Engineering Optimization, Cilt 43, No 2, 135-
• , 2011.
• Edis, E.B. ve Ozkarahan, I. "Solution Approaches
• for a Real Life Resource Constrained Parallel
• Machine Scheduling Problem", International
• Journal of Advanced Manufacturing
• Technology, Cilt 58, No 9-12, 1141-1153, 2012.
• Bourland, K.E. ve Carl, L.K., “Parallel machine
• scheduling with fractional operator
• requirements”, IIE Transactions, Cilt 26, No 5,
• -65, 1994.
• Zouba, M, Baptiste, P. ve Rebaine, D.,
• “Scheduling identical parallel machines and
• operators within a period based changing mode”,
• Computers & Operations Research, Cilt 36,
• -3239, 2009.
• Garey, M.R. ve Johnson, D.S., Computers and
• Intractability: A Guide to the Theory of NPCompleteness,
• W. H. Freeman and Company,
• A.B.D., 1979.
• Darbi-Dowman, K.D., Little, J., Mitra, G. ve
• Zaffalon, M., “Constraint Logic Programming
• and Integer Programming Approaches and Their
• Collaboration in Solving an Assignment
• Scheduling Problem”, Constraints, Cilt 1, 245-
• , 1997.
• Smith, B.M., Brailsford, S.C., Hubbard, P.M. ve
• Williams, H.P., “The Progressive Party Problem:
• Integer Linear Programming and Constraint
• Programming Compared”, Constraints, Cilt 1,
• -138, 1997.
• Darbi-Dowman, K.D. ve Little, J., “Properties of
• Some Combinatorial Optimization Problems and
• Their Effect on the Performance of Integer
• Programming and Constraint Logic
• Programming”, Informs Journal on
• Computing, Cilt 10, No 3, 276-286, 1998.
• Lustig, I.J. ve Puget J.F., “Program Does Not
• Equal Program: Constraint Programming and Its
• Relationship to Mathematical Programming”,
• Interfaces, Cilt 31, No 6, 29-53, 2001.
• IBM, ILOG OPL IDE 6.3., User’s Manual,
• IBM Corp., 2009.
• McNaughton, R., “Scheduling with deadlines and
• loss functions”, Management Science, Cilt 6, No
• , 1-12, 1959.
• Li, Y., Wang, F. ve Lim A., “Resource
• constraints machine scheduling: A genetic
• algorithm approach”, CEC: 2003 Congress on
• Evolutionary Computation, Cilt 1-4, 1080-
• , 2003.