A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS

A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS

(Pendekatan Pemrograman Dinamis untuk Permasalahan Pengurutan)

Michael Held dan Richard M. Karp

Diterjemahkan oleh: Komarudin Tasdik

https://komarudintasdik.wordpress.com

 

 

Pendahuluan

Banyak optimisasi menarik dan penting membutuhkan determinasi order terbaik dari sebuah himpunan operasi. Paper ini berkaitan dengan solusi tiga masalah sequencing: masalah scheduling mencakup fungsi cost arbitrary, masalah traveling-salesman, dan masalah assembly-line balancing. Tiap masalah ini memiliki struktur solusi skema rekursi berhubungan dengan dynamic programming. Pada esensinya, skema rekursi ini cenderung menyebut permasalahan dengan combinations daripada permutations, dalam operasi yang dilakukannya. Formulasi dynamic programming mencakup: 1. Diskusi berbagai ekstensi seperti inklusi kendala utama. Dalam tiap kasus metode solusi yang diharapkan adalah efektivitas komputasional untuk permasalahan dalam suatu range terbatas. Solusi perkiraan untuk permasalahan lebih besar bisa diperoleh dengan menyelesaikan sederet permasalahan yang dibagi menjadi modul-modul kecil, masing-masing modul memiliki struktur yang sama seperti aslinya. Prosedur perkiraan suksesif ini dikembangkan secara rinci, 2. Referensi khusus untuk masalah traveling-salesman, dan 3. Pengalaman komputasi singkat dengan program IBM 7090 menggunakan prosedur tersebut.

  1. Formulasi Masalah

1.1              Scheduling problem. Seandainya kita diberi sederet pekerjaan J1, J2, …, Jn yang dieksekusi berturut-turut pada fasilitas tunggal. Beberapa pekerjaan Jk membutuhkan layanan fasilitas itu untuk Tk unit waktu. Jk juga dihubungkan dengan fungsi ck(t), menjadikan cost-nya berhubungan dengan penyelesaian Jk pada waktu t. Kami berasumsi bahwa fasilitas itu tetap berguna, dan tidak ada pekerjaan yang diinterupsi sebelum selesai.[1] Dengan asumsi ini, beberapa perintah eksekusi pekerjaan (schedule) bisa direpresentasikan dengan perintah (i1 i2…in) bertipe integer dari satu sampai n, menunjukkan bahwa pekerjaan dieksekusi dalam perintah Ji1, Ji2, …, Jin. Diberikan schedule, waktu terminasi tik dari ik adalah  , dan total cost yang berhubungan dengan schedule adalah

(1)

Kita mencari perintah untuk (1) asumsi nilai minimum C

Beberapa penulis menganggap masalah ini sebagai jenis fungsi cost khusus. Contohnya, McNaughton [9] menganggap kasus ini berada pada tiap Ck(t) konstan terhadap poin waktu, dan kemudian bertambah secara linear. Algoritma dynamic programming memperhatikan kebutuhan tanpa asumsi fungsi cost.

S = {k1, k2, …, kn(s)} merupakan himpunan bagian dari {1, 2, …, n} dan disimbolkan dengan ts kuantitas  . C(S) merupakan minimum cost terjadi dalam mengeksekusi pekerjaan Jk1, Jk2, …, Jkn(s), dalam order apapun, dalam interval [0,ts]. Untuk l Î S, S-l merupakan himpunan yang diperoleh dengan menghapus l dari S. Kemudian kita bisa menentukan relasi recurrence berikutnya, di mana C(S), untuk himpunan S, diekspresikan dalam istilah nilai C untuk himpunan bagian S:

(a)    (n(S) =1:                C({l}) = c1(Tl), untuk l

(2)

(b)   (n(S) > 1):              C(S) = minlÎs [C(S-l)+c1(ts)]

Untuk justifikasi ini, kita berargumen sebagai berikut: dalam perintah eksekusi pekerjaan optimal dengan indeks dalam S(contoh, cost C(S)) suatu pekerjaan, sebutlah J1, harus dieksekusi terakhir, dan pekerjaan yang tersisa (yang ditunjukkan dalam S-l) harus dieksekusi secara optimal dalam [0, ts-l]. Kemudian total cost-nya terjadi karena ordering akan menjadi C (S-l)+c1(ts). Mengambil yang minimum dari semua pilihan l, kita mendapatkan (2b)

Ordering (i1 i2…in) adalah optimum jika dan hanya jika,

C({i1, i2, …, ip}) = C({i1, i2, …, ip-1}) + cip(t{i1, i2, …i})

(3)

(2 p n

Prosedur untuk menemukan solusi optimum memiliki dua fase. Fase pertama, quantitias C(S), untuk semua S Í {1, 2, …, n), dihitung secara rekursif dari (2); C diberikan oleh C({1, 2, …, n}). Dalam fase kedua, (3) digunakan untuk menghasilkan optimum ordering (i1 i2 …in); in diperoleh dahulu, dan kemudian, berturut-turut, in-1, in-2, …, i1.

Operasi dasar yang dibutuhkan adalah tambahan dan perbandingan (addition and comparison), yang terjadi dalam jumlah yang sama. Jumlah addition dalam fase pertama dihasilkan oleh ; jumlah addition pada fase kedua adalah . Jika satu lokasi storage untuk masing-masing jumlah C(s), jumlah lokasi yang dibutuhkan adalah 2n-1.

1.2    Traveling-salesman problem

Formulasi dynamic programming tentang scheduling problem harus dipandang berdasarkan fakta bahwa cost terjadi dalam mengeksekusi pekerjaan hanya bergantung pada pekerjaan yang mendahuluinya. Kami sekarang membahas traveling-saleman problem, yang mana memperlihatkan jenis cost dependence yang berbeda.

Traveling-salesman problem merupakan penemuan permutasi P=(1 i2 i3 …in) bertipe integer dari 1 sampai n yang meminimalisir quantitasnya.

(4)   A1i2 + 1i2i3 + ai3i4 + … + ain1

Di mana aµb merupakan himpunan real. Lebih akurat, sejak terdapat hanya (n-1)! kemungkinan berpikir bahwa masalah itu berarti menemukan metode yang efisien untuk memilih permutasi minimal.

“Masalah itu mengambil namanya dari fakta bahwa keinginan salesman untuk travel dengan total jarak terpendek dari rumahnya menuju tiap n-1 kota-kota tertentu, dan kemudian kembali lagi ke rumah, dapat menggunakan metode seperti itu jika dia diberikan jarak aµb di antara pulang-pergi kota dalam tour-nya. Atau, jika salesman itu menginginkan total waktu travel terpendek, aµb akan merepresentasikan waktu travel individual”[6].

Apabila tidak ada metode komputasi yang acceptable dan sempurna untuk mengatasi traveling-salesman problem, beberapa prosedur telah dikembangkan untuk mendapatkan solusi optimum atau mendekati optimum. Bagaimanapun, prosedur-prosedur ini biasanya agak membosankan, intuitif, dan sulit untuk program sebuah komputer. Diskusi “state of the art” tentang traveling-salesman problem bisa dilakukan [1]. Kami mulai memberikan formulasi dynamic programming untuk masalah ini.[2]

Misalkan S Í {2, 3, …, n) dan l Î S, C(S, l) merupakan istilah minimum cost mulai dari satu kota dan mengunjungi semua kota dalam himpunan S, berhenti di cota l. Kemudian

(a)    (n(S) = 1):              C({l}, l) = a1l , untuk setiap l

(5)

(b)   (n(S) > 1):              C(S, l) = minmÎS-l [C(S-l, m) + aml].

Melihat ini, andaikata bahwa, dalam mengunjungi kota-kota itu dalam S, berakhir di kota l, kota m segera mendahului kota l. Kemudian, mengasumsikan bahwa kota-kota lainnya dikunjungi dalam optimum order, cost-nya adalah  C(S-l, m) + aml. Mengambil minimum cost dari semua pilihan m, kita memperoleh (5b). Akhirnya, jika C merupakan minimum cost dari complete tour, mencakup kembalinya ke kota satu,

(6)   C = minlÎ[2, 3, …, n] [C({2, 3, …, n}, l) + al1].

Permutasi (1 i2 i3 … in) optimum jika, dan hanya jika,

(7)   C = C({2, 3, …, n}, in) + ain1

dan, untuk 2 p n-1,

(8)   C({i2, i3, …, ip, ip+1}, ip+1) = C({i2, i3, …, ip}, ip) + aipip+1

Sebagaimana dalam scheduling problem, komputasi dua-fase digunakan untuk memperoleh solusi optimum. Dalam fase pertama, quantitas C(S, l) dikomputasi secara rekursif dari (5), dan C dikomputasi dari (6). Pada fase kedua, (7) dan (8) digunakan untuk mengkomputasi permutasi optimum (in ditentukan dulu, dan kemudian, berturut-turut, in-1, in-2, …, i2).

Juga, operasi dasar yang dikerjakan dalam komputasi itu adalah addition dan comparisons. Jumlah masing-masing dalam fase pertama dimisalkan

.

Jumlah kejadian tiap operasi dalam fase kedua adalah . Jika satu lokasi storage ditetapkan untuk tiap jumlah C(S, l), jumlah lokasi yang dibutuhkan adalah

1.3    Assembly-line balancing problem.

Dalam scheduling and traveling-salesman problems, semua possible orderings dari elemen-elemen tersebut (pekerjaan atau kota) tersedia. Beberapa sequencing problems melibatkan kendala-kendala yang memperlihatkan ordering tertentu yang terjadi. Keuntungan pendekatan dynamic programming adalah bahwa kendala-kendala seperti itu memudahkan solusi tersebut, daripada menghambatnya. Kita mengilustrasikan ini dengan mengacu pada assembly-line balancing problem yang diajukan oleh Salveson [10].

Assembly line dibutuhkan untuk menyelesaikan tiap unit yang ada, sebuah himpunan pekerjaan yang disimbolkan dengan J1, J2, …, Jn. Misalkan pekerjaan Jk bisa dieksekusi dalam Tk units waktu, dan bisa ditetapkan untuk beberapa lokasi (workstations) yang ditempatkan secara serial sepanjang assembly line. Penetapan ini dibuat agar:

(1)   ti, jumlah waktu eksekusi pekerjaan-pekerjaan yang ditugaskan untuk ke-i workstation tidak melebihi cycle time T; T- ti disebut idle time pada station ke-i,

(2)   semua kebutuhan yang lebih utama muncul dari teknologi assembly process (kita asumsikan ini mengambil bentuk “J1 harus mendahului Jm”) terpenuhi,

(3)   jumlah workstations diminimalisir.

Eksistensi kendala-kendala utama direfleksikan dalam notasi-notasi feasible sets dan feasible assignments. Misalkan himpunan bagian S Í {1, 2, …, n} dikatakan feasible jika tidak ada pair (Jl, Jm) seperti (a) l Ï S, (b) m Î S, dan (c) Jl dibutuhkan untuk precede Jm. Assignment pekerjaan untuk workstations 1, 2, …, q disebut feasible, jika, untuk tiap i q, himpunan pekerjaan itu ditetapkan untuk i pertama workstation adalah feasible. Dengan any feasible set S = {k1, k2, …, kn(s)} dihubungkan dengan “cost” C(S), yang minimum, semua feasible assignments dari pekerjaan itu dengan indeks dalam S, dari kuantitas (r-1) T+tr, di mana r adalah jumlah workstations yang dibutuhkan dalam assembly line dan tr adalah jumlah waktu eksekusi pekerjaan yang tetapkan untuk workstation akhir, menurut assignment tertentu. Kemudian quantitas C(S) bisa dikomputasi menurut relasi recurrence berikutnya, yang hold only untuk feasible sets:

(a)    (n(S) = 1): C(l}) = T1

(9)

(b)   (n(S) > 1):

di mana[3]

(i)

(ii)               .

Quantitas Ñ(C(S-l), tl) merupakan incremental cost berkaitan dengan penyelesaian (assigning) pekerjaan Jl, mengasumsikan bahwa pekerjaan itu ditentukan oleh elemen-elemen S – l telah ditentukan dalam cara yang optimum.

Relasi recurrence (9) hampir identik terhadap yang digunakan dalam formulasi scheduling problem (2), dan komputasi dua-fase yang mirip bisa digunakan untuk menghitung C({1, 2, …, n}), dan memperoleh optimum assignment assembly line.[4]

1.4    Some Extensions

Relasi recurrence dilakukan untuk solusi assembly-line balancing problem sangat menyerupai yang diperoleh dalam pembahasan scheduling dan traveling-salesman problems. Bagaimanapun, formulasi line-balancing problem itu, melibatkan relasi dahulu, yang direfleksikan dalam membatasi kelas himpunan bagian yang ditetapkan. Pembatasan utama pada perintah eksekusi pekerjaan yang dijadwalkan, atau pada route traveling salesman, bisa diatasi dengan cara yang serupa.

Variasi lain pada tiga masalah dibawah konsiderasi melibatkan kemungkinan “parallelism”: himpunan kota yang dikunjungi bisa dibagi untuk beberapa salesmen; operasi assembly bisa dibagi menjadi beberapa assembly lines; pekerjaan bisa dijadwalkan pada sebagian beberapa fasilitas. Sebagai ilustrasi tipe situasi ini, kami akan memperkenalkan beberapa modifikasi ke dalam scheduling problem.

Andaikata fasilitas-fasilitas itu F(1), F(2), …, F(v) tersedia. Beberapa pekerjaan Jk bisa dilakukan oleh beberapa fasilitas, dengan waktu eksekusi masing-masing. . Cost yang berkenaan dengan penyelesaian Jk dalam waktu t pada fasilitas F(i) dengan . Kemudian divisi optimum dari pekerjaan di antara fasilitas, bersama dengan optimum schedule untuk tiap fasilitas, diperoleh seperti berikut:

(a)    Untuk tiap himpunan S menghitung fungsi C(i) (S) oleh means dari (2), dengan  disubstitusi untuk tk dan ck(t), berturut-turut, dalam komputasi ke-i.

(b)   Menghitung minimum-nya[5], semua partisi {1, 2, …, n} ke dalam himpunan S(1), S(2), …, S(v), dari quantitas  memisalkan minimum ini terjadi untuk partisi T(1), T(2), …, T(v).

(c)    Dalam optimum schedule, pekerjaan dalam T(i) dilakukan pada F(i). Perintah eksekusi pada tiap fasilitas yang dikomputasi dari (3), seperti sebelumnya.

Jumlah operasi dalam algorithms under discussion bisa sangat direduksi ketika equivalences ditulis di antara elemen untuk di-ordered. Anggap, contohnya, situasi scheduling di mana n pekerjaan dijadwalkan bisa dipartisi ke dalam q equivalence classes, misalnya ada dua pekerjaan dalam kelas sama memiliki waktu eksekusi dan fungsi cost yang sama. Kemudian, sebagian himpunan pekerjaan ditandai oleh vektor V = (v1, v2, …, vq), menetapkan bahwa himpunan itu memuat elemen v1 dalam equivalence class ke-l; bahkan, semua himpunan untuk vektor itu sama bisa dibahas sepertinya. Kemudian, jika tiap kelas himpunan ditentukan oleh vektor V, (2) bisa diganti oleh

(a) C(0, 0, …, 0) = 0

(10)

(b)     C(V) = min1≤l≤q dan vl>0 [C(V-el) + cl(V.t).

Di sini t = (t1, t2, …, tq) di mana tl merupakan waktu eksekusi dari sebuah pekerjaan dalam equivalence class ke-l, cl(t) merupakan fungsi cost untuk pekerjaan dalam equivalence class ke-l, dan V- el merupakan vektor yang diperoleh dengan menguranginya dari komponen ke-l dari V.[6]

  1. Successive Approximations (Perkiraan yang Berturut-Turut)

Karakteristik algorithms under discussion bahwa kompleksitasnya, diukur dengan jumlah operasi aritmetik dan kebutuhan storage, tumbuh sangat cepat. Bagaimanapun, itu adalah kemajuan besar melebihi enumerasi (penyebutan satu per satu) sempurna, dan mengizinkan solusi langsung yang cepat dari permasalahan ukuran layak.[7] Dalam bagian ini kami menampilkan bagaimana algoritma-algoritma itu bisa dikombinasikan dengan metode successive approximation untuk menghasilkan prosedur sistematik dalam menyelesaikan permasalahan besar. Prosedur ini menghasilkan urutan permutasi, masing-masing diperoleh dari predecessor-nya dengan solusi subproblem yang diperoleh dari ukuran layak (moderate size) yang memiliki struktur sama seperti masalah yang diberikan. Cost yang berhubungan membentuk monotone nonincreasing sequence yang tidak bisa bertemu dengan solusi optimum; bagaimanapun, pengalaman komputer telah menghasilkan hasil istimewa dalam variasi kasus (cf. §3). Sebagai ilustrasi, kami akan menentukan metode successive approximation untuk mengatasi permasalahan traveling-salesman besar.

Misalkan permutasi P = (1 i2 … in) merepresentasikan route melalui n kota, kota-kota itu bisa dipartisi ke dalam u ordered sets, masing-masing terdiri dari yang terjadi berturut-turut dalam P, dan memelihara order sama seperti dalam P. Sebuah u-city traveling-salesman problem kemudian diatasidi mana tiap ordered set dianggap sebagai sebuah kota, dan cost-nya berasal dari himpunan (ij ij+1 …ik-1 ik) sampai (il il+1…im-1 im) sama dengan aikil. Jika u tidak terlalu besar dari masalah yang ada ini bisa diatasi dengan algoritma dynamic programming dari §1.2. Solusi itu menyatakan reordering P’ dari P, dengan P’ memiliki cost lebih sedikit dari atau sama dengan P.

Dua jenis partisi telah terbukti sangat bermanfaat. Dalam tipe pertama ini, disebut local partition, tiap ordered sets selain satu yang terdiri dari elemen tunggal, agar tour yang berhubungan dengan P dan P’ berbeda di tempat itu, if at all. Yang ekstrim lainnya, global partition mengambil u sets dalam ukuran sesama mungkin, agar, jika perubahan-perubahan dibuat, akan cenderung menjadi bagian dari global nature. Contoh dari dua jenis partisi ini, dan possible reordering yang berhubungannya, tampak pada Figs. 1a dan 1b. Dalam contoh-contoh ini, n = 16 dan u = 8. Dalam solusi permasalahan besar itu, telah membuktikan diperlukan untuk menggunakan fase pengganti dari kemajuan lokal dan global (local and global improvement).

Melalui pengalaman dengan program kompter, prosedur sistematis untuk seleksi masalah yang adas telah dikerjakan.

(a)    LOCAL, lihat aslinya!

(b)   GLOBAL, lihat aslinya!

FIG. 1. Contoh-contoh local and global improvement, lihat aslinya!

Sebagai bagian dari proses seleksi ini, sebuah  teknik diperoleh untuk menentukan apakah masalah yang ada yang ada sangat mungkin untuk menghasilkan perbaikan/kemajuan (contohnya, cost P’ < cost P). Tiap masalah yang ada ditentukan oleh u x u cost matrix C = (cij), dengan baris dalam kolom untuk masing-masing himpunan kota untuk disusun kembali. Kami asumsikan bahwa baris dan kolom itu bagian dari matrix ini disusun  menjadi slant elements cu1, c12, …, cu-1.u memberikan cost transisi yang terjadi dalam permutasi P terbaru. Jika cost P’ lebih kecil dari cost P, optimum tour untuk traveling-salesman problem yang ada didefinsitikan sebagai C yang harus menggunakan penyesuaian transisi terhadap off-slant elements dari C. Ratio dari slant elements yang mana baris dan kolom minimal menuju total u dari slant elements yang telah terbukti untuk menjadi ukuran handal dari “promise” bagian dari problem yang ada. Pada beberapa poin dalam komputasi, matrik-matrik untuk slant ratio ini melebihi nilai kritis (yang mana bisa diselesaikan sebagai hasil komputasi) tidak dipertimbangkan lebih lanjut.

Jika tidak ada prosedur seleksi seperti itu yang digunakan, bisa ditampilkan bahwa teknik successive approximation menghasilkan tour akhir yang sama untuk dua equivalent traveling-salesman problems. Dua masalah yang berkaitan dengan n x n cost matrices (aij) dan (bij) dikatakan equivalent jika terdapat konstanta µ dan b seperti itu, untuk cyclic permutation T dari indeks 1, 2, …, n, .

Sejak penyesuaian submatriks dari matrik equivalent (aij) dan (bij) tidak harus memiliki slant ratio yang sama, invarians/gabungan komputasi di bawah tranformasi equivalence  hilang ketika seleksi dikerjakan. Bagaimanapun, bisa memperoleh caconical representative untuk tiap equivalence class (lihat lampiran 1) dan invariance, jika diinginkan, bisa dipelihara dengan mentranformasi problem yang ada ke dalam bentuk canonical-nya.

  1. Program Komputer

Dalam bagian ini, kami menghadirkan beberapa hasil komputasi yang diperoleh dengan program IBM 7090 untuk traveling-salesman problem itu. Program ini mengatasi permasalahan yang mencakup 13 atau lebih sedikit kota dengan aplikasi langsung dari algoritma dynamic programming dari §2.

3.1    Spesifikasi

Dalam program yang mengimplementasikan prosedur successive approximation, tiap problem yang ada (derived) adalah bagian dari ukuran 13. Program ini berproses dalam fase penggantian local and global improvement. Tiap fase local improvement membentuk cycle melalui n possible masalah yang ada yang sesuai dengan optimal reordering kota-kota berurutan, hingga full cycle dianggap tanpa improvement apapun. Pada poin ini, slant ratio treshold ditambah, dan, jika tidak melebihi di atas batas yang ditentukan untuk fase terbaru itu, local improvement itu berlanjut; sebaliknya fase global improvement dimasuki. Selama tiap fase global improvement, ketika paling banyak n+1 problems yang ada dipertimbangkan. Pertama dari fase ini diperoleh dengan memilih partisi yang memaksimalkan jumlah slant elements dalam cost matriks yang ada, sehingga cenderung membuat slant ratio kecil. Program itu memilih n remaining problems dengan pasti tapi aturan arbitrary yang membuat ukuran 13 sets sesama mungkin.  Masalah yang ada diuji kembali, dan untuk itu slant ratio tidak melebihi treshold terbaru, kalkulasi dynamic programming dilakukan untuk memperoleh tour yang optimum. Secepat mungkin masalah yang ada menghasilkan sebuah solusi lebih baik daripada yang berhubungan dengan slant-nya, improvement itu digabungkan ke dalam semua masalah, dan fase baru dari local improvement diinisiasi. Jika tidak ada masalah yang menghasilkan sebuah improvement, slant-ratio treshold ditambah, dan, jika itu tidak melebihi di atas batas yang ditentukan untuk fase terbaru (current phase), permasalahan itu diuji kembali; sebaliknya fase baru dari local improvement diinisiasi, dan tidak ada global improvement yang dibuat pada tahapan kalkulasi ini.

Kalkulasi berproses hingga poin penurunan hasil dialami, seperti diukur dengan ukuran pemberhentian empiris mencakup jumlah masalah yang dilakukan dengan algoritma dynamic programming tanpa keberhasilan dalam fase apapun. Dalam beberapa kejadian, program itu diselesaikan setelah fase kelima dari global improvement.

Strategi kalkulasi itu, mencakup pilihan masalah yang ada, penyesuaian slant-ratio tresholds, dan terminasi komputasi, telah disarankan dengan pengalaman komputasional. Secara luas membatasi keberhasilan program yang tidak bergantung pada pilihan-pilihan ini secara kritis.

3.2    Hasil

Kami sekarang menghadirkan enam contoh yang dilakukan dengan program komputer IBM 7090. Dalam contoh-contoh ini, waktu eksekusi untuk run yang berbeda di antara dua menit dan 15 menit. Dalam masing-masing kasus, initial tour itu dipilih secara random.

(i)                  42-city problem dari Dantzig, Fulkerson, dan Johnson. Dalam [4] cost dari tour yang optimal ditampilkan dengan argumen khusus hingga menjadi 699.

Run No. Cost of Initial Tour Cost of Final Tour
1 3235 699
2 3513 705
3 3207 704
4 3246 699
5 2913 704

(ii)                20-city problem due to Croes. Dalam [3], Croes menyatakan bahwa cost dari tour yang optimal adalah 246

Run No. Cost of Initial Tour Cost of Final Tour
1 732 246
2 816 246
3 811 246

(iii)              48-square knight’s tour. Jika jarak di antara dua kotak  papan catur diambil sebagai jumlah minimum dari gerak kuda yang dibutuhkan untuk mencapai satu kotak ke kotak lain, masalah penemuan tour kuda yang rahasia (tour dari papan dengan gerakan-gerakan kuda, seperti tiap kotak yang dikunjungi cukup satu kali, dan berakhir dengan kembali ke kotak awal) bisa dilakukan sebagai traveling-salesman problem. Sejak tour kuda yang tertutup/rahasia diketahui eksis untuk abbreviated 6 x 8 papan catur [8], menyesuaikan dengan traveling-salesman problem yang memiliki solusi optimal dengan cost 48.

Run No. Cost of Initial Tour Cost of Final Tour
1 132 56
2 132 52
3 124 54
4 132 56

(iv)              36-square king’s tour. Tour raja rahasia bisa diformulasikan sebagai traveling-salesman problem dalam cara sama tour raja. Sebenarnya tour raja rahasia berada untuk 6 x 6 papan catur; karenanya, kesesuain traveling-salesman problem memiliki solusi optimum dengan cost 36.

Run No. Cost of Initial Tour Cost of Final Tour
1 87 36
2 103 36

(v)                Tour 48 kotadi USA. Hasil-hasil mesin digabungkan dengan inspeksi visual menyarankan dugaan bahwa tour yang optimal memiliki cost 11,470. Matriks untuk masalah ini dan tour yang diduga optimal tampak dalam Fig. 2.

Lihat Fig. 2. 48-city problem

Lihat Fig. 3. 25-city problem

Run No. Cost of Initial Tour Cost of Final Tour
1 50,716 11,566
2 42,288 12,116
3 45,400 11,984
4 51,223 11,688

(vi)              25-city problem untuk cost tour yang optimal diyakini menjadi 1711. Cost matriks untuk masalah ini dan tour optimal yang mungkin terjadi tampak pada Fig. 3.

Run No. Cost of Initial Tour Cost of Final Tour
1 5626 1711
2 5838 1711
3 5115 1711
  1. KESIMPULAN

Pendekatan dynamic programming dibahas dalam paper ini tanpa pengertian kunci universal untuk solusi sequencing problems. Bagaimanapun, pendekatan itu bisa digunakan dalam sejumlah  situasi penting, dan, ketika dapat diaplikasikan, menawarkan beberapa keuntungan. Untuk permasalahan kecil, solusi optimal bisa diperoleh dengan hanya sejumlah komputasi kecil, dan dapat diprediksi dengan tepat. Permasalahan yang lebih besar sesuai dengan teknik successive-approximation, walaupun justifikasinya kurang kuat, tapi telah benar-benar sukses dalam prakteknya.[8] Akhirnya, teknik-teknik ini bisa dimekanisasi secara sempurna dengan program komputer sederhana.

LAMPIRAN 1

REDUKSI MATRIK MENJADI CACONICAL FORM

Dalam §2, dua n-city traveling-salesman problems ditentukan dengan matriks (aij) dan (bij) disebut equivalent jika ada konstatnta µ dan b, untuk tour T,

Dalam lampiran ini, kami menandai equivalence ini secara langsung dalam istilah penentuan matriks, dan menampilkan bagaimana mendapatkan canonical representative dari tiap equivalence class.

Dalam diskusi berikutnya, tepat mendefinisikan empat kelas matriks khusus: (eij) constant-row matrix (constant-column matrix) jika semua elemennya nol, kecuali untuk baris (kolom) tunggal, semua yang elemen off-diagonal-nya sama (elemen diagonal adalah arbitrary); (eij) adalah potential matrix[9] jika setiap triple i, j, k, eij + ejk ; (eij) adalah matriks image jika elemen diagonalnya sama menuju nol, dan tiap jumlah dan kolomnya sama dengan nol.

Kami sekarang mendefinisikan homomorphic mapping T dari grup aditif G dari n x n (real) matriks pada group aditif G dari n x n (real) matriks image. Misalkan (dij) Î G kami definisikan pemetaan dalam dua langkah:

(1)

(2)    .

Di sini, dlm adalah Kronecker delta dan µ1, µ2, …, µn+1 ditetapkan secara unik  dari sistem n+1 linear equations mengekspresikan syarat bahwa dij = 0 untuk semua i dan  . Dengan mudah terlihat bahwa (dij) kepunyaan G.

Bisa ditampilkan bahwa inti N dari peta T adalah subgrup normal dari G yang dihasilkan oleh himpunan constant-row, constant-column, dan potential matiks. Selanjutnya, dengan hukum homomorfisme group-group [11], bahwa dua matriks memiliki image sama di bawah pemetaan T jika dan hanya jika masing-masing bisa diperoleh dari yang lainnya dengan tambahan constant row, constant columns, dan potential matrix.

Canonical form dari sebuah matriks adalah image-nya di bawah pemetaan T. Dua matriks dikatakan equivalent jika masing-masing bisa diperoleh dari matriks lainnya yang hanya menggunakan operasi berikut: (a) tambahan matriks constant-row dan constant-column, (b) tambahan dari potential matrices, dan (c) perkalian matriks dengan konstanta skalar. Jadi, dua matriks equivalent jika dan hanya jika canonical forms-nya berbeda dengan faktor multiplikatif skalar konstan.

Akhirnya, bisa ditampilkan bahwa dua n x n traveling-salesman problems equivalent jika dan hanya jika penentuan matriksnya equivalent, agar equivalence class dari traveling-salesman problems ditandai dengan canonical form dari salah satu matriks yang saling berhubungan.

Ucapan Terima kasih. Penulis sangat berhutang budi kepada Mr. R. Shareshian dari IBM’s Mathemtics and Applications Department, yang bertanggung jawab besar terhadap persiapan program komputer traveling-salesman yang dibahas di sini. Terima kasih juga kepada Dr.  A. Bomberault dari departemen yang sama atas beberapa stimulasi pembahasan, terutama yang berkaitan dengan representasi canonical yang ada dalam Lampiran 1.

REFERENSI

Sumedang, 17 Nopember 2010


[1] Tidak ada kentungan dalam  melanggar asumsi-asumsi ini ketika fungsi-fungsi ck(t) monotone nondecreasing, merepresentasikan penalties yang terjadi untuk manangguhkan penyelesaian pekerjaan-pekerjaan itu

[2] Formulasi ini, ditemukan secara independen oleh Penulis, secara esensial identik dengan yang diharapan Bellman [2]

[3] [ ] merupakan “integer part of”.

[4] Masalah pemotongan lengths tertentu t1, t2, …, tn stok dari jumlah minimum standard reels of  length T bisa dibahas dengan relasi recurrence yang sama dengan tepat, dengan semua himpunan S yang feasible. Pendekatan pemrograman linear untuk meng-cut  masalah stok lihat [5] dan [7]

[5] Dimungkinkan untuk memberikan algoritma dynamic programming  agar komputasi minimum ini efisien

[6] Divisi dalam equivalence classes ini merupakan device yang sangat berguna dalam masalah cutting stock, di mana biasanya perlu untuk meng-cut beberapa rolls dari length yang sama. Jumlah equivalence class kemudian menjadi sama dengan jumlah length berbeda yang di-cut.

[7] Program IBM 7090 bisa mengatasi 13-city traveling-salesman problem dalam 17 detik.

[8] Program IBM 7090 mengaplikasikan teknik successive approximation untuk masalah scheduling fasilitas tunggal §1.1 telah bertemu dengan kesuksesan yang sebanding dengan yang dibahas di atas tentang  traveling-salesman problem.

[9] Matriks potensial mendefinisikan traveling-salesman problem untuk cost tour rahasia yang bernilai nol.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s