AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ

M. Emin BAYSAL, Taha DURMAZ, Ahmet SARUCAN, Orhan ENGİN
1.730 340

Öz


Açık Atölye Tipi Çizelgeleme (AATÇ) problemi temelde, her bir işin her makinede işlem görmesi gerekensadece bir işleminin bulunduğu ve işlem sırasının önemli olmadığı bir çizelgeleme problemidir. Çoğunluklabenzer ürün gruplarının üretildiği tesislerde görülmektedir. Bu çalışmada, AATÇ problemleri toplamtamamlanma zamanının minimizasyonuna yönelik, rassal zıplama tekniği ile işleyen Paralel KanguruAlgoritması (PKA) ile çözülmüştür. PKA, sürekli daha iyi çözümlere ulaşmaya çalışan meta-sezgisel biryöntemdir. Literatürde yer alan AATÇ; kıyas problemleri, vahşi ve evcil iki kanguru operatörünün paralelçalıştırıldığı, Kanguru Algoritması (KA) ile çözülmüştür. Elde edilen değerler, literatürde daha önce ulaşılan eniyi sonuçlar ile karşılaştırılmıştır. PKA’nın AATÇ problemlerinin çözümünde etkin bir yöntem olduğubelirlenmiştir.

Anahtar kelimeler


Açık atölye tipi çizelgeleme, paralel kanguru algoritması, tamamlanma zamanı.

Tam metin:

PDF


Referanslar


Liaw, C.F., Cheng, C.Y., Chen, M., “The total

completion time open shop scheduling problem

with a given sequence of jobs on one machine”,

Computers & Operations Research, 29, 1251

– 1266, 2002.

Durmaz, T., Açık Atölye Çizelgeleme

Problemlerinin Paralel Kanguru Algoritması

ile Çözümü, Yüksek Lisans Tezi, Selçuk

Üniversitesi, Fen Bilimleri Enstitüsü, 2011.

Gonzalez, T., Sahni, S., “Open shop scheduling

to minimize finish time”, Journal of the ACM,

(4):665–79, 1976.

Arıkan, M., Erol, S., “A long term memory tabu

search algorithm for part selection and machine

loading in flexible manufacturing systems”,

Journal of The Faculty of Engineering and

Architecture of Gazi University, 25, 2, 311-

, 2010.

Dereli, T., Daş, G. S., “Ant colony optimization

approach for container loading problems”,

Journal of The Faculty of Engineering and

Architecture of Gazi University, 25, 4, 881-

, 2010

Liaw, C.F., “An efficient tabu search approach

for the two-machine preemptive open shop

scheduling problem”, Computers &

Operations Research, 30, 2081–2095 2003.

NG, C.T., Cheng, T.C.E., Yuan, J.J., “Concurrent

Open Shop Scheduling to Minimize the

Weighted Number of Tardy Jobs”, Journal of

Scheduling, 6, 405 – 412, 2003.

Blum, C., “Beam-ACO—hybridizing ant colony

optimization with beam search: an application

to open shop scheduling”, Computers &

Operations Research, 32, 1565–1591, 2005.

Shabtay, D., Kaspi, M., “Minimizing the

Makespan in Open-Shop Scheduling Problems

with a Convex Resource Consumption

Function,” Wiley InterScience (2 February

.

Senthilkumar, P., Shahabudeen, P., “GA based

heuristic for the open job shop scheduling

problem”, Int J Adv Manuf Technol, 30, 297–

, 2006.

Sedeno-Noda, A., Alcaide, D., Gonzalez-

Martin, C., “Network flow approaches to preemptive

open-shop scheduling problems with time-windows”, European Journal of

Operational Research, 174, 1501–1518, 2006.

Gribkovskaia, I.V., Lee, C.Y., Strusevich, V.A.,

Werra, D., “Three is easy, two is hard: open

shop sum-batch scheduling problem refined”,

Operations Research Letters, 34, 459 – 464,

Sha, D.Y., Hsu, C.Y., “A new particle swarm

optimization for the open shop scheduling

problem”, Computers & Operations

Research, 35 3243 – 3261, 2008.

Brasel, H., Herms, A., Mörig, M., Tautenhahn,

T., Tusch, J., Werner, F., “Heuristic

constructive algorithms for open shop

scheduling to minimize mean flow time”,

European Journal of Operational Research,

, 856–870, 2008.

Lin, H.T., Lee, H.T., Pan, W.J., “Heuristics for

scheduling in a no-wait open shop with movable

dedicated machines”, Int. J. Production

Economics, 111, 368–377, 2008.

Mosheiov, G., Oron, D., “Open-shop batch

scheduling with identical jobs”, European

Journal of Operational Research, 187, 1282–

, 2008.

Werra, D., Kis, T., Kubiak, W., “Preemptive

open shop scheduling with multiprocessors:

polynomial cases and applications”, J Sched 11,

–83, 2008.

Sedeño-Noda, A., Pablo, D.A.L., González-

Martín, C., “A network flow-based method to

solve performance cost and makespan openshop

scheduling problems with time-windows”,

European Journal of Operational Research,

, 140–154, 2009.

Low, C. ve Yeh, Y., “Genetic algorithm-based

heuristics for an open shop scheduling problem

with setup, processing, and removal times

separated”, Robotics and Computer-

Integrated Manufacturing, 25, 314–322,

Akgöbek, Ö., Kaya, S., Değirmenci, Ü., Engin,

O., “Açık Atölye Tipi Çizelgeleme

Problemlerinin Paralel Doyumsuz Metasezgisel

Algoritma ile Çözümü”, Bilimde Modern

Yöntemler Sempozyumu – BMYS 2010, 14-

Ekim Dicle Üniversitesi Kongre Merkezi,

-130, 2010.

Naderi, B., Ghomi, S.M.T.F., Aminnayeri, M.,

Zandieh, M., “A contributon and new heuristics

for open shop scheduling”, Computers &

Operations Research, 37, 213-221, 2010.

Zhang, X. ve Velde, S., “On-line two-machine

open shop scheduling with time lags”,

European Journal of Operational Research,

14–19, 2010.

Türkeli, B., “Solution of Bicriteria Open Shop

Scheduling Problem with Genetic Algorithm

and Tabu Search and Detailed Analysis of

Results”, Yüksek Lisans Tezi, Marmara

University Institute For Graduate Studies In

Pure And Applied Sciences, İstanbul, 2010.

Kökçam, A.H. ve Engin, O., “Bulanık Proje

Çizelgeleme Problemlerinin Meta Sezgisel

Yöntemlerle Çözümü”, Mühendislik ve Fen

Bilimleri Dergisi (Sigma), 28, 86-101, 2010.

Serbencu, A., Minzu, V., Serbencu, A., “An Ant

Colony System Based Metaheurıstic for Solving

Single Machine Scheduling Problem”, The

Annals of “Dunarea De Jos” Unıversity Of

Galati Fascicle III, Electrotechnıcs,

Electronıcs, Automatıc Control, Informatıcs, 19-

, 2007.

Teske, E., “Computing discrete logarithms with

the parallelized kangaroo method”, Discrete

Applied Mathematics, 130, 61-82, 2003.

Pollard, J.M., “Kruskal's Card Trick”, The

Mathematical Gazette, 84, 500 (Jul.), 265-267,

Jellouli, O., Chatelet, E., “Monte Carlo

Simulation And Stochastich Algorithms For

Optimising Supply Chain Management in an

Uncertain Environment”, Systems, Man, and

Cybernetics, 2001 IEEE International

Conference, 3 1840-1844. 2001.

Stein, A. ve Teske, E., “The Parallelized Pollard

Kangaroo Method in Real Quadratic Function

Fields”, Mathematics of Computation, 71/238

-814, 2001.

Minzu, V. ve Beldiman, L., “Some aspects

concerning the implementation of a parallel

hybrid metaheuristic”, Engineering

Applications of Artificial Intelligence, 20,

–999, 2007.

Yılmaz, M.K., Kökçam, A.H., Duvarcı, V.,

Fığlalı, A., Ayöz, M., Engin, O., “Paralel

Kanguru Algoritması Yardımıyla Beklemesiz

Akış Tipi Çizelgeleme Problemlerinin

Çözümü”, Yöneylem Araştırması ve Endüstri

Mühendisliği 29. Ulusal Kongresi, 2010.

Yılmaz, M.K., Engin, O., Fığlalı, A., Yavuz,

M., “Parallel Kangaroo Algorithm For Biobjective

Flow Shop Scheduling with a New

Weight Combining Approach”, 1st

International Symposium on Computing in

Science & Engineering, ISCSE-2010, Gediz

University (İzmir), June 3-5, Kuşadası Aydın

Turkey, 823-827, 2010.

Yılmaz, M.K., Fığlalı, A., Terzi, U., Yavuz, M.,

Engin, O., “A Hybrid Parallel Kangaroo a

&Simulated Annealing Algorithm for Multi-

Objective Flow Shop Scheduling” The Journal

of Management and Engineering Integration,

, 2, 2010.

Guéret, C., Prins, C., “A new lower bound for

the open-shop problem”, Annals of Operations

Research, 92:165–83, 1999.

Guéret, C., Ecole des mines de Nantes – Open

shop problems [online], Nantes, Ecole des

mines de Nantes, http://www.minesnantes.

fr/en/Media/ Elements-Sites-

Persos/Christelle-Gueret/Openshop/

HardOSInstances [Ziyaret Tarihi: 3 Ocak

.




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.