Semoga tesis ini dapat bermanfaat bagi pembaca dan pihakpihak lainnya yang

Akhir kata penulis menyadari bahwa tesis ini masih jauh dari sempurna. Untuk itu penulis mengharapkan kritik dan saran untuk penyempurnaan tesis ini. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihakpihak lainnya yang memerlukannya.

Medan,

Juni 2013

Penulis,

Yenny Hermiana Alga

v

Universitas Sumatera Utara

RIWAYAT HIDUP

Penulis dilahirkan di Takengon Kabupaten Aceh Tengah pada Tanggal 4 Juni 1988 dan merupakan anak kedua dari tiga bersaudara dari Bapak Hasanuddin dan Ibu Salmiah, S.Pd. Penulis menamatkan Sekolah Dasar di SD Negeri Buntul Kubu Takengon lulus tahun 2000, Sekolah Menengah Pertama di SMP Negeri 1 Takengon lulus tahun 2003, Sekolah Menengah Atas di SMA Negeri 2 Modal Bangsa Aceh Besar lulus Tahun 2006. Pada Tahun 2006 penulis melanjutkan pendidikan Diploma Statistika di Universitas Sumatera Utara dan lulus tahun 2009. Penulis melanjutkan pendidikan Sarjana di Universitas Sumatera Utara pada Fakultas Matematika dan Ilmu Pengetahuan Alam jurusan Matematika lulus tahun 2011. Selanjutnya pada tahun 2011 penulis berkesempatan untuk melanjutkan program Master pada Program Studi Magister Matematika di Universitas Sumatera Utara.

vi


ABSTRAK Dalam kerangka kerja penjadwalan mesin terdapat kemungkinan adanya suatu interval waktu dimana suatu unit pekerjaan tidak dapat diproses. Penelitian ini mendiskusikan model deterministik penjadwalan dalam persoalan bin packing pada mesin tunggal identik dengan adanya interval waktu dalam zona terlarang. Dalam penelitian ini ditunjukkan suatu model penjadwalan yang layak atau optimal terhadap pekerjaan dengan memperhatikan interval waktu dalam zona terlarang. Model yang diperoleh dinyatakan dalam bentuk program linier dengan objektif model adalah meminimumkan total waktu penyelesaian (makespan) sehingga diperoleh minimum interval waktu dalam zona terlarang yang dinyatakan ke dalam bentuk program integer. Keyword: Penjadwalan, Zona terlarang, Jobshop, Bin packing problem

i


ABSTRACT In machine scheduling of manufacturing systems there may be a certain time interval, during which jobs processing may not be continued. This research discuss a deterministic model of bin packing problem scheduling on a single identical machine by considering a time interval in forbidden zones. This research represents a feasible or optimal scheduling of jobs by considering any time interval in forbidden zones. The model that formulated into linear programming with objective is minimized the completion time (makespan) in order to obtain time interval minimum in forbidden zones that represents by integer programming. Keyword: Scheduling, Forbidden zones, Jobshop, Bin packing problem

ii


DAFTAR ISI Halaman KATA PENGANTAR

iii

RIWAYAT HIDUP

vi

ABSTRAK

i

ABSTRACT

ii

DAFTAR ISI

iii

DAFTAR GAMBAR

v

DAFTAR TABEL

vi

BAB 1 PENDAHULUAN

1

1.1 Latar Belakang

1

1.2 Perumusan Masalah

3

1.3 Tujuan Penelitian

4

1.4 Manfaat Penelitian

4

BAB 2 KAJIAN PUSTAKA

5

2.1 Klasifikasi Persoalan Penjadwalan

5

2.1.1 Persoalan penjadwalan

5

2.1.2 Data unit pekerjaan dalam penjadwalan

7

2.1.3 Karakteristik penjadwalan

9

2.1.4 Kriteria optimalitas dalam penjadwalan 2.2 Penjadwalan Mesin

10 12

2.2.1 Definisi penjadwalan mesin

12

2.2.2 Ruang lingkup mesin

13

2.2.3 Penjadwalan mesin tunggal identik

17

2.3 Persoalan Jobshop

19

2.4 Penjadwalan Flowshop

21 iii


2.4.1 Persoalan bin packing

25

2.5 Zona Terlarang dalam Penjadwalan

26

BAB 3 PROGRAM INTEGER

31

3.1 Program Linier

31

3.2 Program Integer

32

3.3 Persoalan Penjadwalan dalam Program Integer

32

BAB 4 PENJADWALAN MESIN DENGAN ADANYA ZONA TERLARANG

35

4.1 Model Penjadwalan Mesin dengan Adanya Zona Terlarang

35

4.2 Contoh Kasus

38

BAB 5 KESIMPULAN DAN SARAN

40

5.1 Kesimpulan

40

5.2 Saran

40

5.3 Riset Lanjutan

40

DAFTAR PUSTAKA

41

iv


DAFTAR GAMBAR

Nomor

Judul

Halaman

2.1

(i.) Orientasi mesin terhadap pekerjaan pada skema Gantt 1

5

2.2

(ii.) Orientasi pekerjaan terhadap mesin pada skema Gantt 2

6

2.3

Ilustrasi Jobshop pada satu mesin

14

2.4

Penjadwalan flowshop yang layak pada mesin

23

2.5

Ilustrasi penjadwalan yang mungkin dari Lemma 1, (a),(b) dan (c)

24

2.6

Ilustrasi interval waktu dan zona terlarang dalam penjadwalan

27

2.7

Ilustrasi penjadwalan mesin tunggal dengan waktu awal dalam zona terlarang

29

v


DAFTAR TABEL

Nomor 2.1

Judul Ilustrasi Data

Halaman 23

vi


BAB 1 PENDAHULUAN

1.1 Latar Belakang Secara umum, penjadwalan didefinisikan sebagai suatu proses dalam menentukan penugasan suatu himpunan operasi atau pekerjaan ke pusat berdasarkan pada interval atau periode waktu. Objektif dari persoalan penjadwalan adalah untuk menentukan suatu m barisan penjadwalan dari seluruh pekerjaan QJk yang ada pada mesin Mk , k = 1, 2, . . . , m dengan nilai pada fungsi objektif yang diberikan, φ(C1 , C2, . . . , Cn ) adalah minimum. Karena itu, persamaan Ci = cini dan Ci menyatakan waktu total penyelesaian pekerjaan Ji ∈ J. Penjadwalan pada sejumlah mesin identik dengan tujuan untuk meminimumkan total waktu penyelesaian pekerjaan (makespan) yang merupakan satu dari persoalan umum yang sering dikaji dalam optimisasi kombinatorial. Persoalan penjadwalan yang telah dikembangkan oleh para peneliti banyak digunakan dalam kegiatan produksi suatu perusahaan, mesin dan sebagainya. Dalam beberapa kasus tertentu, terdapat beberapa kebijakan tertentu yang mempengaruhi pengambilan keputusan, maka proses ini akan menambahkan suatu kendala waktu, batas waktu operasi atau total waktu pekerjaan secara keseluruhan ke dalam model rancangan yang ada (Chaudhuri, 1995). Salah satu persoalan penjadwalan yang umum dikaji merupakan persoalan penjadwalan minimum makespan yang selanjutnya disebut dengan persoalan bin packing. Andaikan terdapat batasan waktu pada rancangan operasi secara keseluruhan dengan memberikan batas waktu pada masing-masing pekerjaan yang ada. Dalam sistem penjadwalan suatu perusahaan terdapat beberapa persoalan yang menjadi kendala dalam kegiatan produksi, salah satunya berkaitan dengan informasi akurat diUniversitas Sumatera Utara

1

2 mana suatu unit pekerjaan yang akan diproses dapat diselesaikan dalam suatu interval waktu tertentu. Persoalan ini termasuk persoalan yang kompleks dimana proses pengambilan keputusan mempengaruhi penjadwalan perusahaan tersebut. Kendala waktu ini selanjutnya disebut sebagai suatu zona terlarang (forbidden zones) dalam persoalan penjadwalan. Abdekhodaee dan Ernst (2004) juga memberikan pandangan mengenai penjadwalan dengan adanya kendala waktu yang selanjutnya disebut sebagai zona terlarang (forbidden zones). Asumsikan terdapat n pekerjaan yang dijadwalkan sebagai J1 , J2, . . . , Jn dengan pi sebagai waktu proses Ji . Interval waktu dibagi menjadi I = {I1, . . . , Is } sehingga tiap Ij merupakan bagian dari zona terlarang yang dinotasikan sebagai Fi ⊂ Ij ,∀j. Akibatnya, interval waktu Ij \ Fj adalah interval waktu yang diizinkan. Khammuang et al. (2007) menambahkan bahwa zona terlarang dalam persoalan penjadwalan menjelaskan adanya suatu interval waktu selama suatu pekerjaan tertentu tidak dapat diproses. Lebih jelasnya, andaikan terdapat suatu pekerjaan yang sudah selesai tepat sebelum interval waktu yang termasuk ke dalam zona terlarang. Selanjutnya pekerjaan tersebut akan keluar dari barisan urutan penjadwalan pada interval waktu berikutnya. Akibatnya, waktu penyelesaian akhir dari suatu pekerjaan pada Ij dapat dinyatakan sebagai t = 2j − 1. Dalam penelitian tesis ini mendiskusikan model deterministik dimana kendala dalam penjadwalan adalah pi , i = 1, . . . , n total jumlah bin yang diberikan dengan pi mempunyai nilai rasional (0, 1]. Tujuan dari persoalan ini adalah mengurutkan penjadwalan seluruh pekerjaan dengan variasi waktu proses masing-masing pekerjaan ke total mesin yang digunakan dalam meminimumkan makespan dengan memperhatikan batasan atau kendala interval waktu dalam penjadwalan mesin yang termasuk dalam zona terlarang (forbidden zones). Penelitian tesis ini difokuskan pada diskusi dari model deterministik untuk penjadwalan mesin Universitas Sumatera Utara

3 tunggal identik dengan adanya interval waktu dalam zona terlarang yang direpresentasikan ke dalam bentuk program linier. Hasil yang diperoleh merupakan model program linier dengan kendala penjadwalan yang merupakan suatu program integer yang digunakan dalam mengurutkan total pekerjaan yang tersedia Ji ke dalam penjadwalan mesin tunggal identik yang layak. Penulisan tesis ini disusun sebagai berikut: Bab I menjelaskan latar belakang dan masalah yang dikaji dalam penelitian tesis ini. Bab II kajian teori serta beberapa riset yang relevan dengan penelitian tesis ini. Bab III berupa penjelasan mengenai teori program integer yang digunakan dalam model penjadwalan. Bab IV mengkaji hasil diskusi model deterministik untuk penjadwalan mesin tunggal identik dengan adanya interval waktu dalam zona terlarang (forbidden zones). Bab V memberikan kesimpulan dan saran dari hasil penelitian tesis untuk penelitian selanjutnya yang mungkin dapat dikembangkan. 1.2 Perumusan Masalah Salah satu pengembangan model penjadwalan dengan adanya zona terlarang (forbidden zones) telah dilakukan sebelumnya oleh Khammuang et al. (2007). Kekurangan dari model yang telah dikembangkan oleh Khammuang et al. (2007) adalah model hanya difokuskan pada penjadwalan on-line dengan zona terlarang di waktu awal proses pekerjaan. Penelitian ini mendiskusikan model deterministik penjadwalan dalam persoalan bin packing pada mesin tunggal identik yang dapat digunakan untuk mengurutkan seluruh pekerjaan Ji (i = 1, . . . , n) dalam meminimumkan total waktu penyelesaian (makespan) dengan adanya kendala interval waktu yang termasuk ke dalam zona terlarang.


4 1.3 Tujuan Penelitian Tujuan penelitian ini adalah mendiskusikan metode deterministik penjadwalan Ji (i = 1, . . . , n) pekerjaan pada mesin tunggal identik sehingga diperoleh suatu barisan penjadwalan yang layak. Model kemudian direpresentasikan dalam menyelesaikan persoalan bin packing dan menentukan total waktu penyelesaian (makespan) minimum penjadwalan dengan kendala interval waktu yang termasuk ke dalam zona terlarang. 1.4 Manfaat Penelitian Manfaat dari penelitian diharapkan dapat diterapkan dalam proses penyelesaian J pada n total pekerjaan sehingga model dalam penelitian ini dapat meminimumkan total waktu penyelesaian yang diperlukan meskipun terdapat asumsi interval waktu tertentu sebagai zona terlarang. Selanjutnya, model juga diharapkan dapat membantu proses pengambilan keputusan dalam pengurutan dan memprioritaskan suatu set atau himpunan pekerjaan. Hal ini merupakan salah satu konsep literatur manajemen operasi dimana suatu metode solusi cepat, sederhana dan efektif dapat digunakan untuk menyelesaikan beberapa atau seluruh pekerjaan yang ada.


BAB 2 KAJIAN PUSTAKA

2.1 Klasifikasi Persoalan Penjadwalan Teori dan beberapa istilah yang digunakan dalam penelitian ini dirujuk dari beberapa jenis persoalan penjadwalan yang telah dikaji sebelumnya. Pada bab ini, beberapa klasifikasi dasar dalam persoalan penjadwalan dikaji secara luas seperti yang telah dikaji dalam literatur (lihat Lawler et al., 1993). 2.1.1 Persoalan penjadwalan Asumsikan terdapat m mesin Mj (j = 1, . . . , m) yang digunakan untuk memproses n unit pekerjaan Ji (i = 1, . . . , n). Suatu penjadwalan pada masing-masing unit pekerjaan yang dialokasikan pada satu atau lebih interval waktu ke satu atau lebih mesin yang ada. Penjadwalan tersebut dapat direpresentasikan dengan menggunakan skema Gantt seperi yang ditunjukkan pada Gambar 2.1 berikut.

Gambar 2.1 : (i.) Orientasi mesin terhadap pekerjaan pada skema Gantt 1


5

6

Gambar 2.2 : (ii.) Orientasi pekerjaan terhadap mesin pada skema Gantt 2

Objektif dari persoalan penjadwalan berdasarkan skema Gantt adalah menentukan penjadwalan didasarkan pada orientasi jumlah mesin dan unit pekerjaan yang ada sebagai kendala dalam penjadwalan. Secara umum, persoalan penjadwalan dapat diklasifikasikan dengan menggunakan suatu notasi yaitu α|β|γ, dengan α merupakan total jumlah mesin yang ada, β adalah karakteristik suatu pekerjaan dan γ menyatakan kriteria optimalitas (Graham et al., 1979). Menurut Graham et al. (1979), terdapat beberapa parameter yang relevan dalam pemodelan suatu mesin, yaitu pj sebagai waktu pemrosesan suatu pekerjaan j, rj adalah waktu penyelesaian pekerjaan j yang telah ditentukan, sizej menyatakan total jumlah mesin atau prosesor yang dibutuhan untuk menyelesaikan pekerjaan j dan pmtn yang menyatakan preemption dalam model penjadwalan. Parameter ini menjadi gagasan untuk mengimplementasikan model ke dalam suatu algoritma yang selanjutnya disebut dengan algoritma on-line. Algoritma ini didasarkan pada fakta bahwa suatu pekerjaan yang tersedia pada suatu rentang waktu tertentu dapat diselesaikan, dan sebaliknya. Selanjutnya, Megow et al. (2006) melakukan pengembangan terhadap model penjadwalan secara stokastik dalam menentukan suatu aturan penjadwalan stokastik online dalam meminiP mumkan nilai ekspektasi pada waktu penyelesaian pekerjaan, E [ wj Cj ]. Dalam model terdapat asumsi adanya waktu proses distribusi Pj yang saling bebas, sehingga diperoleh bahwa rj < rk untuk j < k. Suatu aturan penjadwalan memUniversitas Sumatera Utara

7 berikan suatu spesifikasi tindakan terhadap pekerjaan pada waktu keputusan t dengan waktu awal adalah t dan waktu keputusan berikutnya dinotasikan sebagai t0 > t. Untuk suatu contoh I, dimana terdapat total jumlah mesin m, himpunan pekerjaan J dengan masing-masing waktu penyelesaian yang ditentukan rj , bobot wj dan waktu proses distribusi Pj , ambil SjΠ (I) dan CjΠ (I) sebagai variabel acak waktu awal dan waktu penyelesaian pekerjaan dibawah ketentuan Π. Sehingga diperoleh aturan penjadwalan secara stokastik sebagai # " X X wj CjΠ (I) = wj E[CjΠ (I)] E[Π(I)] = E j∈J

j∈J

yang kemudian disebut dengan model penjadwalan online stokastik (SoS). 2.1.2 Data unit pekerjaan dalam penjadwalan Suatu unit pekerjaan diselesaikan pada ni operasi Oi1 , . . . , Oi,ni . Oij yang selanjutnya dialokasikan oleh waktu proses yang diperlukan, pij . Jika suatu unit pekerjaan Ji terdapat tepat satu operasi (ni = 1), maka dapat diidentifikasikan bahwa Ji dengan Oi1 dan denotasikan waktu proses yang diperlukan adalah pi . Lebih lanjut, terdapat waktu rilis ri suatu unit pekerjaan, dimana operasi awal Ji tersedia untuk diproses. Alokasikan tiap operasi Oij yang merupakan suatu himpunan mesin µij ⊂ {M1 , . . . , Mm } untuk diproses. Pada umumnya, µij merupakan himpunan satu elemen atau sama dengan himpunan jumlah mesin yang digunakan. Pada dasarnya, suatu operasi Oij dapat diproses pada sebarang mesin yang ada. Persoalan seperti ini merupakan persoalan penjadwalan dengan Multi-Purpose Machines (MPM). Sehingga, ini memungkinkan bahwa semua mesin pada himpunan µij digunakan secara simultan oleh Oij selama interval waktu proses berlangsung yang lebih dikenal sebagai persoalan penjadwalan multiprosesor.


8 Dalam operasi Oij terdapat fungsi biaya fi (t) dalam menentukan biaya proses unit pekerjaan Ji pada waktu t. Batas waktu di dan bobot unit pekerjaan wi dapat digunakan dalam mendefinisikan fungsi fi . Secara umum, seluruh data pi , pij , ri , di , wi diasumsikan dalam suatu bilangan bulat. Suatu penjadwalan adalah layak jika • tidak terdapat dua interval waktu yang bekerja secara bersamaan pada mesin yang sama, • tidak terdapat dua interval waktu yang dialokasikan pada unit pekerjaan yang sama, • dan jika, dalam perluasan, terdapat sejumlah karakteristik persoalan penjadwalan tertentu yang dispesifikasi Dan suatu penjadwalan adalah optimal jika dapat meminimumkan kriteria-kriteria optimalitas yang diberikan dalam persoalan. Teorema 2.1.1 Andaikan G = (V, E, w) merupakan suatu sistem penugasan. Terdapat suatu penjadwalan yang layak pada G jika dan hanya jika G tidak mempunyai cycle. Bukti Berikut bukti pada Teorema 1: ⇒

Asumsikan G mempunyai satu cyclce v1 → v2 → · · · → vk → v1. Maka, v1 ≺ v1 dan suatu penjadwalan yang layak σ adalah σ(v1) + w(v1 ) ≤ σ(v1) haruslah benar, dimana hasil yang diperoleh adalah w(v1) > 0.

⇐

Jika G merupakan asiklik, maka terdapat beberapa unit pekerjaan yang tidak dialokasikan ke mesin yang tersedia. Sehingga dapat dialokasikan terlebih dahulu. Lebih jelasnya, secara topologi verteks-verteks dan menentukan penjadwalan pada mesin yang sama. Universitas Sumatera Utara

9 2.1.3 Karakteristik penjadwalan Menurut Brucker (2007), dalam persoalan penjadwalan, terdapat beberapa karakteristik pekerjaan yang dispesifikasikan oleh suatu himpunan β yang memuat paling banyak enam elemen, yaitu β1, β2, β3, β4, β5 dan β6 . Beberapa karakteristik tersebut antara lain sebagai berikut:

β1

: mengindikasikan apakah preemption (atau pembagian pekerjaan) diperbolehkan dalam suatu penjadwalan. Ini berarti bahwa proses penyelesa an pekerjaan dapat diinterupsi dan kemudian dilanjutkan, meskipun pada mesin yang berbeda dimana pekerjaan dapat diinterupsi beberapa kali. Jika preemption diperbolehkan, set β1 = pmtn.

β2

: mendeskripsikan adanya penjadwalan bersyarat pada pekerjaan (precedence relations) yang direpresentasikan oleh suatu graf asiklik berarah G = (V, A) dengan V = {1, . . . , n} dipasangkan dengan pekerjaan yang ada, dan (i, k) ∈ A jika dan hanya jika Ji telah selesai sebelum Jk dimulai. Dalam kasus ini dapat dinyatakan dengan Ji → Jk dan set untuk β2 = prec.

β3

: jika β3 = ri , maka waktu rilis dapat dispesifikasikan untuk tiap pekerjaan.

β4

: mendeskripsikan adanya batasan pada waktu pemrosesan atau jumlah operasi pekerjaan yang diselesaikan pada waktu tertentu. Jika β4 sama dengan pi = 1(pij = 1), maka tiap pekerjaan mempunyai ketentuanketentuan unit proses.

β5

: jika β5 = di , maka terdapat batas akhir (deadline) masing-masing pekerjaan Ji dengan ketentuan bahwa pekerjaan Ji haruslah diselesaikan tidak lebih lama dari waktu di .

β6

: mengindikasikan total jumlah waktu maksimum penyelesaian semua pekerjaan. Universitas Sumatera Utara

10 Dimana terdapat suatu graf paralel yang berkaitan dengan graf pohon (tree). Suatu graf adalah seri-paralel jika memenuhi aturan sebagai berikut:

Graf dasar

: Sebarang graf yang terdiri dari suatu verteks tunggal adalah seri-paralel. Ambil Gi = (Vi , Ai) sebagai seri-paralel pada indeks (i = 1, 2).

Komposisi paralel : Graf G = (V1 ∪ V2 , A1 ∪ A2) yang terbentuk dari G1 dan G2 dengan menggabungkan himpunan verteks dan arcs. Komposisi seri

: Graf G = (V1 ∪ V2 , A1 ∪ A2 ∪ T1 × S2 ) yang terbentuk dari G1 dan G2 dengan menggabungkan himpunan verteks dan arcs dan menjumlahkan seluruh arcs (t, s) dimana t adalah bagian himpunan T1 dan s adalah bagian dari himpunan S2 .

Teorema 2.1.2 (Coffman, 1976) Asumsikan G = (V, E, w) sebagai graf asiklik berarah, p menyatakan jumlah prosesor dan σp sebagai suatu penjadwalan pada G. Maka,

1 MSopt (p) MS(σp) ≤ 2 − p

(2.1)

2.1.4 Kriteria optimalitas dalam penjadwalan

Definisi 1 Penjadwalan pada suatu sistem penugasan G = (V, E, w) merupakan suatu fungsi waktu σ : V → N∗ dengan ketentuan: ∀(u, v) ∈ E, σ(u) + w(u) ≤ σ(v)

Definisi 2 (Legrand, 2004) Total jumlah waktu yang diperlukan untuk menyelesaikan seluruh pekerjaan (makespan) pada suatu penjadwalan merupakan total jumlah waktu eksekusi yang dapat dinyatakan sebagai (Legrand, 2004) Total jumlah waktu yang diperlukan untuk menyelesaikan seluruh pekerjaan (makespan) Universitas Sumatera Utara

11 pada suatu penjadwalan merupakan total jumlah waktu eksekusi yang dapat dinyatakan sebagai MS(σ) = max{σ(v) + w(v)} − min{σ(v)} v∈V

v∈V

Makespan juga dinotasikan sebagai Cmax = max Cv . v∈V

Terdapat dua persoalan utama dalam menentukan solusi makespan dalam persoalan penjadwalan, yaitu: P b(p)

: menentukan penjadwalan dengan makespan minimum yang paling mungkin dengan menggunakan paling banyak p prosesor atau mesin. MSopt (p) menyatakan makespan optimal dengan menggunakan p prosesor.

P b(∞) : menentukan penjadwalan dengan makespan paling minimum dimana jumlah prosesor yang digunakan tidak mempunyai batas. Persoalan ini dapat dinyatakan sebagai MSopt (∞) berdasarkan pada persoalan makespan. dengan beberapa penaksiran yang dapat ditentukan dalam jobshop antara lain sebagai berikut. Flow time (Fj )

: Total jumlah waktu yang diperlukan pekerjaan j pada sistem penjadwalan mesin

Makespan

: Total jumlah waktu yang diperlukan untuk menyelesaikan seluruh pekerjaan

Lateness (Lj )

: Total jumlah waktu dimana waktu penyelesaian pekerjaan berbeda dari waktu yang telah ditentukan

Tardiness (Tj )

: Total jumlah waktu dimana waktu penyelesaian pekerjaan j tidak sesuai dengan waktu yang ditentukan atau sama dengan 0, yaitu Tj = max{0, L}. Universitas Sumatera Utara

12 Dari definisi diatas diperoleh formula untuk menentukan penaksiran dalam persoalan jobshop yaitu

Mean Flow time

n 1 P Fj : F¯ = n j=1

Mean Tardiness

n 1 P : T¯ = Tj n j=1

Maksimum Flow time

: Fmax = max {Fj }

Maksimum Tardiness

: Tmax = max {Tj }

Jumlah pekerjaan yang terkendala

: NT =

1≤j≤n

1≤j≤n

n P

f (Tj )

j=1

dengan f (Tj ) = 1 jika Tj > 0 dan f (Tj ) = 0 untuk lainnya. 2.2 Penjadwalan Mesin 2.2.1 Definisi penjadwalan mesin Asumsikan terdapat graf bipartit lengkap G = (V1 ∪ V2 , V1 × V2 ) dengan V1 = {v1, . . . , vn } dan V2 = {w1, . . . , wn } dengan n ≤ m. Untuk masing-masing arc (vi, wj ) terdapat suatu bilangan riil cij , sehingga diperoleh pemetaan satusatu ϕ : V1 → V2 yang merupakan suatu persoalan penjadwalan ϕ dengan fungsi objektif yaitu min

X

cυϕ (υ)

(2.2)

v∈V1

Persoalan penjadwalan tersebut dapat direpresentasikan oleh suatu matriks dimensi n × m C = (cij ) dan diformulasikan sebagai suatu program linier dengan


13 nilai 0-1 variabel xij yaitu min

m n X X

kendala

i=1 j=1 m X

cij xij

xij = 1,

j=1 n X

i = 1, . . . , n (2.3)

xij ≤ 1,

j = 1, . . . , m

i=1

xij ∈ {0, 1},

i = 1, . . . , n; j = 1, . . . , m

dengan xij = 1 jika dan hanya jika vi dipasangkan ke wj . Untuk masing-masing kendala yang terdapat dalam persamaan 2.5, tiap vi ∈ V1 dipasangkan ke tiap elemen di V2 , dan tiap wj ∈ V2 terdapat sedikitnya pada satu penjadwalan yang ada. 2.2.2 Ruang lingkup mesin Ambil nilai α1 ∈ {o, P, Q, R, P MP M, QMP M} dengan o didenotasikan sebagai simbol kosong (sehingga, α = α2jikaα1 = o), maka tiap Ji mempunyai suatu operasi tunggal. Brucker (2007) mengemukakan ruang lingkup mesin diklasifikasikan oleh notasi α = α1 α2 pada dua parameter yang digunakan. Jika α − 1 = o, tiap unit pekerjaan diproses pada satu mesin identik yang dirujuk. Jika α1 ∈ {P, Q, R}, maka terdapat mesin paralel dimana tiap unit pekerjaan dapat diproses oleh masing-masing mesin M1 , . . . , Mm . Jika α1 = P , maka terdapat mesin paralel identik. Sehingga, untuk waktu proses pij pada unit pekerjaan Ji di Mj diperoleh pij = pi untuk semua mesin Mj . Jika α1 = Q, maka terdapat mesin paralel uniform dengan pij = pi /sj dengan sj adalah kecepatan kinerja mesin Mj . Terakhir, jika α1 = R, maka terdapat mesin paralel yang saling bebas dengan pij = pi /sij untuk kecepatan unit pekerjaan yang saling berkaitan sij pada Mj . Jika α1 ∈ {G, X, O, J, F }, maka terdapat model suatu multi-operasi dalam penjadwalan yang dialokasikan ke tiap unit pekerjaan Ji jika terdapat suatu himpunan operasi Oi1 , . . . , Oi,ni . Mesin yang digunakan dirujuk dimana seluruh µij meruUniversitas Sumatera Utara

14 pakan himpunan dengan elemen 1. Persoalan ini selanjutnya disebut persoalan general shop. Indikasikan persoalan general shop dengan set α1 = G. Jobshop, flowshop, open shop dan mixed shop merupakan persoalan khusus dari persoalan general shop. Dalam persoalan jobshop, indikasikan α1 = J, maka diperoleh suatu relasi operasi yaitu Oi1 → Oi2 → Oi3 → · · · → Oi,ni ,

i = 1, . . . , n

(2.4)

Gambar 2.3 : Ilustrasi Jobshop pada satu mesin

Lebih lanjut, secara umum dapat diasumsikan bahwa µij 6= µi,j+1 untuk j = 1, . . . , ni − 1. Disebut sebagai persoalan jobshop dimana µij = µi,j+1 merupakan perulangan mesin pada jobshop yang mungkin.


15 Flowshop diindikasikan oleh α1 = F dengan ni = m untuk i = 1, . . . , n dan µij = {Mj } untuk masing-masing i = 1, . . . , n dan j = 1, . . . , m.

Open shop dinotasikan dengan α1 = O dengan definisi yang hampir sama dengan flowshop dengan tanpa ada relasi antara operasi tiap unit pekerjaan yang ada.

Mixed shop diindikasikan dengan α1 = X yang merupakan kombinasi dari jobshop dan open shop.

Suatu permutasi flowshop merupakan suatu flowshop dimana unit pekerjaan diproses secara bersamaan pada masing-masing mesin. Andaikan terdapat suatu persoalan jobshop, maka set β4 sama dengan ni ≤ 2. Pada kasus ini seluruh unit pekerjaan mempunyai paling banyak dua operasi dalam penjadwalan. Jika α2 sama dengan suatu bilangan bulat positif 1, 2, . . . , maka α2 didenotasikan sebagai jumlah mesin yang tersedia. Jika α2 = k, maka k merupakan suatu nilai pendekatan pada jumlah mesin yang tersedia. Jika nilai pendekatan pada jumlah mesin, set α2 = o. Megow and Schulz (2004) mengembangkan suatu model dalam persoalan penjadwalan untuk meminimumkan waktu penyelesaian rata-rata suatu pekerjaan pada mesin paralel identik dengan menggunakan algoritma on-line. Diasumsikan bahwa terdapat suatu mesin paralel identik m dimana tiap mesinnya hanya dapat menyelesaikan satu dari n pekerjaan pada rentang waktu tertentu. Masing-masing pekerjaan dari suatu himpunan J = {j1 , . . . , jn } mempunyai waktu penyelesaian positif pj > 0 dan suatu bobot nonnegatif wj ≥ 0. Sehingga fungsi objektif dalam n P wj Cj dimana Cj menyatakan waktu dimana pekerjaan j telah model adalah j=1

selesai pada suatu penjadwalan yang layak.


16 Mastrolili dan Svensson (2011) memberikan pandangan terhadap persoalan penjadwalan didasarkan pada persoalan jobshop dan flowshop. Dalam persoalan jobshop, asumsikan bahwa terdapat n pekerjaan yang dapat diselesaikan oleh m pada himpunan M mesin yang diberikan. Tiap pekerjaan j mempunyai siklus operasi µj yaitu O1j , O2j , . . . , Oµj j dimana operasi dilakukan pada unit waktu pij tanpa ada interupsi atau gangguan pada mesin mij ∈ M. Diberikan suatu penjadwalan yang layak dimana seluruh operasi telah dijadwalkan dengan ketentuan bahwa tiap mesin dapat bekerja paling banyak hanya satu operasi pada suatu rentang waktu tertentu. Asumsikan Cj sebagai waktu dimana seluruh operasi pada j telah selesai, maka objektif dari model ini adalah meminimumkan makespan Cmax xj Cj dan meminimumkan total jumlah waktu penyelesaian operasi secara P keseluruhan, wj Cj . Sedangkan persoalan penjadwalan flowshop, F kγ, masingmasing pekerjaan diselesaikan oleh tepat satu buah mesin dan seluruh pekerjaan diselesaikan dalam waktu bersamaan yang merupakan suatu contoh kasus yang khusus pada persoalan penjadwalan jobshop yang asiklik. Yamada (2007) memberikan notasi head dan tail pada operasi unit pekerjaan yang belum dijadwalkan. Ambil i sebagai operasi pada mesin Mk yang belum dijadwalkan. Operasi i dapat diidentifikasi sebagai suatu node i ke dalam graf untuk memilih Sp . Ambil ri sebagai panjang dari jarak terpanjang dari unit pekerjaan head ke tail dengan ri = L(0, i) dimana L(i, j) merupakan panjang dari node i ke j yang menyatakan waktu rilis unit pekerjaan. Ambil qi sebagai panjang path dari i ke waktu proses yang diperlukan qi = L(I, ∗) − pi dimana pi menyatakan waktu proses pada i dan qi adalah unit pekerjaan tail pada operasi i. Batas waktu di = L(0, ∗) − qi . Dalam penjadwalan mesin tunggal dapat


17 diformulasikan ke dalam bentuk persamaan matematika sebagai berikut: min max{si + pi + qi } i∈C

Kendala si ≥ ri sj − si ≥ pi ∨ si − sj ≥ pj

(i ∈ C)

(2.5)

(i, j ∈ C)

2.2.3 Penjadwalan mesin tunggal identik Andaikan ri dan pi masing-masing menyatakan jumlah pekerjaan pada himpunan Oij dan waktu proses untuk tiap pekerjaan. Kemudian asumsikan fi merupakan fungsi monoton pada waktu penyelesaian Ci pada pekerjaan i = 1, . . . , n, dimana penjadwalan menentukan tiap pekerjaan ke n waktu proses pekerjaan. Jika waktu proses t dipasangkan ke pekerjaan i, maka fungsi monoton yang diperoleh adalah fi (t + 1). Selanjutnya untuk waktu proses maksimum pekerjaan n, maka persoalan penjadwalan dapat diselesaikan dalam waktu O(n3 ). Karena fungsi fi adalah monoton tak turun, maka ti waktu proses pada n pekerjaan dapat ditentukan dengan menggunakan algoritma dimana terdapat asumsi bahwa semua pekerjaan dienumerasikan sebagai berikut r1 ≤ r2 ≤ · · · ≤ rn

(2.6)

Algoritma Waktu Proses n Pekerjaan

1. t1 := r1 ; 2. FOR i := 2 TO n DO ti := max{ri , ti−1 + 1}

Terdapat suatu penjadwalan optimal dengan waktu proses ti (i = 1, . . . , n). Ambil penjadwalan optimal S dengan waktu proses t1, . . . , tj dimana j < n adalah maksimum, maka tj+1 menunjukkan waktu proses selanjutnya dimana suatu pekerjaan dapat dijadwalkan. Jika tidak terdapat waktu proses untuk tj+1 di S, Universitas Sumatera Utara

18 maka suatu penjadwalan di S dapat dijadwalkan dan dipindahkan ke tj+1 tanpa adanya penambahan pada nilai objektif. Oleh sebab itu, penjadwalan baru yang diperoleh juga optimal dan diperoleh suatu kontradiksi ke maksimalitas pada j. Graf bipartif lengkap yang menyatakan suatu penjadwalan diberikan oleh V1 = {1, . . . , n} dan V2 = {t1, . . . , tn } dengan nilai cij ditentukan oleh    fi (tj + 1) jika ri ≤ tj cij =   ∞ dan lainnya

(2.7)

Teorema 2.2.1 (Brucker, 2007) Asumsikan (cij ) adalah matriks berdimensi n × m dengan n ≤ m. Selanjutnya, asumsikan bahwa cij ≤ cik untuk semua i dan j < k. Maka, xij =

   1   0

jika i = j dan lainnya

merupakan solusi optimal untuk penjadwalan.

Bukti Asumsikan y = (yij ) sebagai solusi optimal dari persoalan penjadwalan dengan yvv = 1 untuk v = 1, . . . , i dimana i dengan nilai sebesar mungkin. Asumsikan i < n (jika i = n). Karena yi+1,i+1 = 0, terdapat suatu indeks l > i + 1 dengan yi+1,l = 1. Selanjutnya, perhatikan bahwa terdapat dua kasus.

1. Kasus 1. Terdapat suatu indeks j > i + 1 dengan yj,i+1 = 1, maka ci+1,i+1 + cjl ≤ ci+1,l + cj,i+1 Sehingga, jika ditentukan     1 jika r = s = i + 1 atau r = j, s = l     y¯rs = 0 jika r = i + 1, s = l atau r = j, s = i + 1       yrs dan lainnya Universitas Sumatera Utara

19 maka y¯rs adalah solusi optimal untuk persoalan penjadwalan, kontradiksi dengan maksimalitas pada i. 2. Kasus 2. yv,i+1 = 0 untuk semua v ≥ i + 1. Terdapat l > i + 1 dengan yi+1,l = 1. Lebih lanjut, ci+1,i+1 ≤ ci+1,l , maka y¯rs didefinisikan oleh     1 jika r = s = i + 1     y¯rs = 0 jika r = i + 1, s = l       yrs dan lainnya merupakan suatu solusi optimal, kontradiksi dengan maksimalitas pada i.

2.3 Persoalan Jobshop Dalam persoalan penjadwalan jobshop, suatu pekerjaan dapat diselesaikan oleh mesin pada sebarang urutan dimana terdapat m mesin dan n pekerjaan yang akan diproses. Yamada (2007) memberikan pandangan mengenai persoalan penjadwalan jobshop yaitu terdapat n×m minimum-makespan yang merupakan topik umum dalam persoalan penjadwalan, yang dapat dinotasikan dengan n/m/G/Cmax . Sehingga dapat dideskripsikan oleh suatu himpunan yang menyatakan n jumlah pekerjaan yang ada, {Ji }1≤j≤n , yang akan diproses oleh m mesin yang dinotasikan dengan suatu himpunan {Mr }1≤r≤m . Objek dari persoalan ini adalah menentukan waktu minimum yang diperlukan untuk menyelesaikan n pekerjaan yang ada yang juga disebut dengan makespan, yang dinotasikan sebagai Cmax =

max

i≤j≤n,1≤r≤m

cjr ,

dengan Ojr dan cjr berturut-turut menyatakan waktu awal dan waktu penyelesaian.


20 Definisi 3 (Definisi Jobshop) Andaikan M sebagai suatu himpunan mesin yang tersedia. Suatu pekerjaan di M merupakan suatu tripel J = (k, µ, d) dimana k ∈ N merupakan jumlah tahap di J, µ : {1 . . . k} → M yang menunjukkan suatu mesin yang digunakan pada tiap tahap, dan d : {1 . . . k} → N yang menunjukkan panjang tiap tahap. Suatu jobshop merupakan suatu himpunan J = {J 1, . . . , J n } untuk pekerjaan J i = (k i , µi , di ).

Definisi 4 (Penjadwalan layak) Asumsikan J = {J 1, . . . , J n } sebagai pekerjaan yang tersedia. Suatu penjadwalan yang layak untuk J merupakan suatu relasi S ⊂ J × K × T sehingga (i, j, t) ∈ S menunjukkan bahwa suatu pekerjaan J i dalam keadaan ’sedang diproses’ pada waktu tahap ke-j untuk waktu t dan, karena itu, digunakan mesin µi (j). Asumsikan Tji sebagai himpunan waktu dimana pekerjaan i ∈ J dieksekusi pada tahap ke-j dengan Tji = {t : (i, j, t) ∈ S}. Suatu penjadwalan haruslah memenuhi beberapa kondisi sebagai berikut:

1. Proses penyelesaian pekerjaan Jika (i, j, t) ∈ S dan (i, j 0, t0) ∈ S, maka j < j 0 juga berakibat t < t0 . 2. Covering Untuk setiap i ∈ J dan j ∈ K, berlaku Z

dt ≥ di (j)

t∈Tji

untuk setiap tahap dalam penjadwalan dieksekusi. 3. Mutual eksklusi Untuk setiap i, i0 ∈ J , j, j 0 ∈ K dan t ∈ T . Jika (i, j, t) ∈ S dan (i0 , j 0, t0) ∈ 0

S, maka µi (j) 6= µi (j 0 ) yang menunjukkan bahwa terdapat dua tahap dari pekerjaan yang berbeda yang diproses atau dieksekusi pada waktu yang sama namun tidak menggunakan mesin yang sama. Universitas Sumatera Utara

21 Teorema 2.3.1 Misal U adalah himpunan pekerjaan yang dapat dijadwalkan terlebih dahulu dan misal i adalah pekerjaan yang bukan merupakan bagian dari U dengan dj ≤ di , ∀j ∈ U . Maka himpunan pekerjaan V = U ∪{i} dapat dijadwalkan jika dan hanya jika x(di ) +

dX i −m

(m − hU (t)) ≥ m

t=1

dimana m adalah jumlah operasi dan di adalah pembagian waktu terhadap penjadwalan mesin.

Teorema 2.3.2 Misal I1 merupakan subhimpunan dari I = {J1 , . . . , Jn }. Batas bawah dari nilai minimum makespan untuk penjadwalan satu mesin dapat ditentukan oleh h(I1) = min ri + i∈I1

X i∈I1

pi + min qi i∈I1

dengan ri , pi dan qi menyatakan waktu awal, waktu penyelesaian dan batas waktu tiap pekerjaan i secara berturut-turut.

Dalam jobshop, asumsikan terdapat suatu pekerjaan α1 = J, sehingga diperoleh suatu kondisi bersyarat (precendence relations) yang dinyatakan sebagai Oi1 → Oi2 → Oi3 → . . . Oi , ni

untuk

i = 1, . . . , n

Selanjutnya, secara umum asumsikan bahwa µij 6= µi,j+1 untuk j = 1, . . . , ni − 1. Akibatnya, µij = µi,j+1 merupakan suatu persoalan jobshop dengan repetisi mesin. 2.4 Penjadwalan Flowshop Persoalan penjadwalan flowshop merupakan suatu persoalan penjadwalan umum dengan

• untuk tiap pekerjaan i terdapat m pekerjaan yang dinyatakan dengan himpunan Oij dimana tiap pekerjaan mempunyai waktu proses pij (j = 1, . . . , m) dan diproses pada mesin Mj , dan Universitas Sumatera Utara

22 • terdapat kendala dengan ketentuan Oij → Oi,j+1 (i = 1, . . . , m − 1) untuk tiap i = 1, . . . , n dimana tiap pekerjaan diproses dengan urutan mesin 1, mesin 2, mesin 3 dan seterusnya.

Oleh karena itu, objektif dalam persoalan ini adalah untuk menentukan urutan pekerjaan φj untuk masing-masing mesin j sehingga diperoleh suatu penjadwalan yang layak. Suatu penjadwalan flowshop disebut juga dengan suatu permutasi flowshop dimana terdapat suatu urutan pekerjaan khusus φ1, φ2 , . . . , φm dengan φ1 = φ2 = · · · = φm . Brucker (2007) menunjukkan suatu bentuk permutasi yang dinyatakan dengan L : L(1), . . . , L(n) untuk semua pekerjaan yang tersedia untuk penjadwalan flowshop dimana terdapat urutan pekerjaan yang sama pada mesin yang berbeda. Asumsikan terdapat suatu urutan optimal dengan aturan urutan kiri mesin yaitu T : L(1), . . . , L(t) dan urutan kanan mesin, R : L(t + 1), . . . , L(n) sedemikian hingga T dan R diproses oleh mesin secara bertahap. Untuk setiap proses, asumsikan suatu pekerjaan Oi∗j∗ dengan waktu proses terendah pi∗j∗ . Jika j ∗ = 1, maka ambil pekerjaan i∗ dari urutan akhir T kemudian ubah T dengan T ◦ i∗. Selanjutnya yntuk yang lainnya ambil i∗ dari urutan awal R kemudian ubah R dengan i∗ ◦ R. Dari asumsi diatas, Brucker (2007) mengemukakan algoritma yang dapat digunakan dalam menentukan urutan pekerjaan sebagai berikut.

Step 1. X := 1, ..., n; T := φ : R := φ Step 2. while X 6= φ DO Step 3. BEGIN Step 4. Tentukan i∗, j ∗ dengan pi∗ j ∗ = min{pij |i ∈ X; j = 1, 2}; Step 5. IF j ∗ = 1, maka T := T ◦ i∗ . ELSE R := i∗ ◦ R; Universitas Sumatera Utara

23 Step 6. X := X \ {i∗ } Step 7. END; Step 8. L := T ◦ R

Brucker (2007) memberikan ilustrasi penjadwalan mesin untuk persoalan penjadwalan flowshop seperti pada tabel 2.1.

Tabel 2.1 : Ilustrasi Data Pekerjaan i Mesin pi1 1 4 2 3 3 3 4 1 5 8

Mesin pi2 8 3 4 4 7

Dengan ketentuan algoritma yang telah diperoleh, maka penjadwalan yang layak yang mungkin dalam urutan pekerjaan yang ada diberikan pada gambar 3.1 di bawah ini.

Gambar 2.4 : Penjadwalan flowshop yang layak pada mesin


24 Selanjutnya, diberikan dua lemma untuk membuktikan bahwa algoritma berlaku untuk persoalan penjadwalan flowshop sebagai berikut.

Lemma 2.4.1 Asumsikan L := L(1), . . . , L(n) sebagai urutan pekerjaan yang ada, sehingga berlaku min{pi1 , pj2 } < min{pj1 , pi2 } yang menunjukkan bahwa pekerjaan i diproses sebelum pekerjaan j di L.

Bukti Jika pi1 < min{pj1 , pi2 }, maka pi1 < pi2 yang menunjukkan pekerjaan i di T . Jika pekerjaan j ditambahkan ke urutan R, maka urutan pekerjaan di T telah selesai. Dan selanjutnya, j diproses setelah i di T karena pi1 < pj1 . Jika pj2 < min{pj1 , pi2 }, diperoleh penjadwalan yang sama. Penjadwalan ini dapat diilustrasikan dengan gambar 2.2 seperti di bawah ini.

Gambar 2.5 : Ilustrasi penjadwalan yang mungkin dari Lemma 1, (a),(b) dan (c)


25 Lemma 2.4.2 Asumsikan terdapat suatu penjadwalan dimana pekerjaan j dijadwalkan segera setelah pekerjaan i. Maka, min{pj1 , pi2 } ≤ min{pi1 , pj2 } menunjukkan bahwa i dan j dapat diganti tanpa mempengaruhi waktu proses pekerjaan.

Bukti Jika j dijadwalkan segera setelah pekerjaan i, maka terdapat tiga kondisi penjadwalan yang mungkin. Notasikan bahwa wij adalah total waktu periode dari pekerjaan i diproses hingga j, maka diperoleh wij = max{pi1 + pj1 + pj2 , pi1 + pi2 + pj2 + pi2 , pj2 } = max{pi1 + pj2 + max{pj1 , pi2 }, x + pi2 + pj2 } Kemudian untuk kondisi max{−pi1 , −pj2 } ≤ max{−pj1 , −pi2 } ambil pi1 + pi2 + pj1 + pj2 ke kedua kondisi di atas, sehingga diperoleh pj1 + pi2 + max{pi1 , pj2 } ≤ pi1 + pj2 + max{pj1 , pi2 } dimana wji < wij . Maka, terbukti bahwa pergantian urutan pekerjaan antara i dan j tidak mempengaruhi waktu proses pekerjaan.

2.4.1 Persoalan bin packing Salah satu persoalan penjadwalan flowshop yang sering dikaji adalah persoalan bin packing merupakan persoalan penjadwalan minimum makespan dengan tujuan mengurutkan seluruh pekerjaan yang ada ke total mesin yang digunakan sehingga diperoleh total minimum bin yang digunakan dalam penjadwalan layak yang diperoleh. Universitas Sumatera Utara

26 Definisi 5 (bin packing) Diberikan pekerjaan dengan bobot s1, . . . , sn ∈ (0, 1]. Alokasikan keseluruhan pekerjaan ke total jumlah minimum bin yang mungkin, dimana tiap bin berbobot 1.

2.5 Zona Terlarang dalam Penjadwalan Asumsikan terdapat suatu penjadwalan yang layak dengan operasi atau pekerjaan Oij ∈ QJ dimulai pada waktu sij dengan waktu penyelesaian secara keseluruhan adalah cij = sij + pij , dimana pij menyatakan waktu proses pekerjaan Oij . Asumsikan QJk sebagai himpunan yang menyatakan seluruh pekerjaan dari himpunan QJ , QJk ⊂ QJ , yang diproses oleh mesin Mk ∈ M. Dalam model deterministik, waktu proses pij diberikan untuk semua pekerjaan Oij , Ji ∈ J dengan j = 1, 2, . . . , ni . Oleh sebab itu, suatu penjadwalan didefinisikan sebagai suatu himpunan waktu awal sij (atau waktu penyelesaian cij ) pada seluruh pekerjaan QJ . Terdapat suatu himpunan waktu penyelesaian pada pekerjaan QJ yang digunakan untuk menyatakan suatu barisan penjadwalan khusus untuk waktu penyelesaian QJk untuk setiap mesin Mk , k = 1, 2, . . . , m. Oleh sebab itu, pada suatu penjadwalan khusus diberikan m barisan penjadwalan khusus untuk pekerjaan QJk untuk setiap mesin Mk ∈ M. Objektif dari persoalan penjadwalan adalah untuk menentukan suatu m barisan penjadwalan dari seluruh pekerjaan QJk yang ada pada mesin Mk , k = 1, 2, . . . , m dengan nilai pada fungsi objektif yang diberikan, φ(C1 , C2, . . . , Cn ) adalah minimum. Karena itu, persamaan Ci = cini dan Ci menyatakan waktu total penyelesaian pekerjaan Ji ∈ J. Andaikan terdapat batasan waktu pada rancangan operasi secara keseluruhan dengan memberikan batas waktu pada masing-masing pekerjaan yang ada. Maka proses ini akan menambahkan suatu kendala waktu, batas waktu operasi atau total waktu pekerjaan secara keseluruhan ke dalam model rancangan yang Universitas Sumatera Utara

27 ada (Chaudhuri, 1995). Kendala waktu ini selanjutnya disebut sebagai suatu zona terlarang (forbidden zones) dalam persoalan penjadwalan. Khammuang et al. (2007) memberikan suatu kendala interval waktu yang berbeda dari model-model penjadwalan yang telah dikembangkan sebelumnya. Dalam beberapa persoalan penjadwalan, proses penyelesaian terhadap pekerjaan tetap berjalan namun tanpa adanya inisialisasi terhadap interval waktu tertentu. Denotasikan bahwa n pekerjaan dapat dijadwalkan menjadi J1 , J2, . . . , Jn . Asumsikan bahwa pi sebagai waktu penyelesaian pekerjaan Ji sehingga pi ≤ 1, ∀i. Sehingga terdapat partisi waktu sebagai suatu himpunan I = {I1 , I2, . . . , Is } dengan I1 = [0, 2], I2 = [2, 4] hingga Is = [2s − 2, 2s].

Masing-masing Ij

merupakan bagian dari zona terlarang (forbidden zones) Fj ⊆ Ij , ∀j dimana F1 = (1, 2], F2 = (3, 4], . . . , Fs = (2s − 1, 2s]. Akibatnya, interval waktu Is Fj merupakan interval waktu yang diperbolehkan (allowed zones) dimana pekerjaan dapat diproses oleh mesin. Lebih sederhana, interval waktu dan zona terlarang dalam penjadwalan dapat diilustrasikan sebagai berikut.

Gambar 2.6 : Ilustrasi interval waktu dan zona terlarang dalam penjadwalan

Khammuang et al. (2007) secara khusus memberikan pandangan terhadap definisi zona terlarang dalam penjadwalan sebagai suatu interval waktu dimana suatu pekerjaan atau operasi tidak dapat dilakukan, namun dapat diproses. Lebih jelasnya, andaikan suatu pekerjaan telah selesai sebelum interval waktu pada zona terlarang, maka pekerjaan tersebut akan dikeluarkan dari himpunan urutan pekerjaan pada interval waktu berikutnya. Sehingga, untuk pekerjaan paling akhir dari suatu barisan urutan pekerjaan yang ada memerlukan waktu penyelesaian Universitas Sumatera Utara

28 t = 2j − 1. Model ini bertujuan untuk menentukan urutan atau barisan terhadap pekerjaan yang ada sehingga diperoleh interval waktu minimum yang digunakan. Billaut dan Sourd (2001) mengembangkan model penjadwalan dengan adanya suatu kendala interval waktu menggunakan asumsi terdapat suatu himpunan waktu awal dalam zona terlarang (forbidden start time) yang diberikan pada persoalan jobshop. Lebih jelasnya, dalam persoalan jobshop, waktu awal dalam zona terlarang didasarkan pada waktu yang ditentukan saat mesin akan menyelesaikan suatu pekerjaan j dengan keadaan mesin tidak dapat melakukan proses lainnya di waktu yang sama. Billaut dan Sourd (2001) memberikan ilustrasi terhadap persoalan penjadwalan yang melibatkan multi mesin, diasumsikan seorang operator dapat melakukan pengaturan mesin. Operator tidak dapat melakukan pekerjaan lainnya dalam waktu yang bersamaan meskipun waktu yang diperlukan untuk menyelesaikan pekerjaan tersebut hanya sedikit. Oleh sebab itu, kedua pekerjaan tersebut tidak dapat diselesaikan pada waktu yang bersamaan sehingga waktu awal dalam zona terlarang menjadi parameter dalam pembagian waktu penjadwalan.

Teorema 2.5.1 (Billaut, 2001) Penjadwalan mesin tunggal dengan adanya waktu awal dalam zona terlarang merupakan persoalan NP-complete.

Bukti (berdasarkan Billaut, 2001) Untuk membuktikan Teorema 5, asumsikan terdapat n = 3m pekerjaan yang dibagi menjadi dua bagian, yaitu:

• 3m pekerjaan pertama dengan waktu penyelesaian s(a). m pekerjaan masingmasing dinotasikan sebagai T1, T2, . . . , Tm • m pekerjaan yang dinotasikan sebagai T1, T2, . . . , Tm dengan waktu penyelesaian sama dengan B


29 Total interval waktu awal dalam zona terlarang adalah K = m(B − 1). Himpunan S interval waktu awal dalam zona terlarang diberikan oleh F = 1≤i≤m [(2i − 1)B + 1, 2iB−1], sehingga secara berkala terdapat B+1 waktu awal diluar zona terlarang dan selanjutnya B − 1 interval waktu awal dalam zona terlarang seperti yang ditunjukkan pada Gambar 2.4 dengan F1 = B + 1, F2 = B + 2, . . . , FB−1 = 2B − 1, FB = 3B + 1 dan seterusnya. Persoalan ini merupakan persoalan pseudo-

Gambar 2.7 : Ilustrasi penjadwalan mesin tunggal dengan waktu awal dalam zona terlarang polynomial dengan total waktu awal dalam zona terlarang didasarkan pada B yang menunjukkan bahwa persoalan merupakan NP-complete. Teorema 2.5.2 (Billaut, 2001) Persoalan 1|Sj 6∈ F, pj = p|Cmax dapat diselesaikan secara optimal dalam waktu O(K), asumsikan bahwa terdapat suatu waktu awal dalam zona terlarang. Bukti Dalam persoalan ini, semua pekerjaan yang ada adalah indentik sehingga tidak terdapat suatu persoalan antrian. Persoalan yang ada adalah untuk menjadwalkan suatu waktu awal yang tidak termasuk dalam F ke tiap pekerjaan yang ada. Jika tidak terdapat suatu waktu awal yang terlarang sama dengan 0( mod p), semua pekerjaan dapat disusun tanpa adanya waktu idle. Sebaliknya, suatu waktu idle terdapat dalam persoalan dan jika terdapat suatu waktu awal terlarang sama dengan 1( mod p), pekerjaan yang ada dapat disusun tanpa ada suatu waktu idle. Proses ini membutukan K iteraksi dan kembali pada suatu nilai optimal makespan. Prosedur ini memberikan optimal makespan dalam O(K) waktu. Universitas Sumatera Utara

30 Teorema 2.5.3 (Billaut, 2001) Jika K = 1, maka terdapat suatu penjadwalan optimal mesin pada makespan adalah P dengan pi = p untuk semua pekerjaan dan F1 = kp untuk beberapa bilangan bulat k < n. Akibatnya, makespan dalam penjadwalan adalah P + 1.

Bukti (berdasarkan Billaut, 2001). Jika waktu proses semua pekerjaan adalah p dan F1 = kp, jelas bahwa tidak terdapat suatu penjadwalan yang layak yang diselesaikan pada P = np. Andaikan suatu penjadwalan pekerjaan ke-k+1 dengan waktu awal kp yang merupakan interval dalam zona terlarang, maka diperoleh suatu penjadwalan yang diselesaikan pada P +1 dengan memulai pekerjaan ke-k+1 pada waktu kp+1. Sekarang akan ditunjukkan bahwa terdapat suatu penjadwalan yang dapat diselesaikan pada P . Jika waktu pemrosesan pada seluruh pekerjaan adalah p dan F1 6= kp, maka tiap pekerjaan dimulai pada waktu kp dengan 0 ≤ k ≤ n − 1 dan sebarang urutan pekerjaan adalah layak dan dapat diselesaikan pada P . Jika terdapat dua pekerjaan yang berbeda dalam suatu penjadwalan, maka dapat diasumsikan bahwa p1 6= p2 dimana p1 ≥ pi , ∀i. Ambil k sebagai indeks dimana Pk−1 ≤ F1 < Pk . Sehingga, diperoleh Pk − F1 ≤ pk ≤ pi . Jika Pk − F1 < p1 , maka pekerjaan yang ada dapat dijadwalkan menjadi J2 , . . . , Jk antara 0 dan Pk − p < F1 dan J1 antara Pk − p1 dan Pk . Jika Pk − F1 = p1 , maka pekerjaan dapat dijadwalkan sebagai J3 , . . . , Jk antara 0 dan Pk − p1 − p2 < F1 dan J1 antara Pk − p1 − p2 dan Pk − p2 = F1 + p1 − p2 6= F1 . Akibatnya, J2 dapat diselesaikan pada Pk − p2 . Pada kedua kasus tersebut, dapat diperoleh penjadwalan untuk J1, . . . , Jk yang dapat diselesaikan sebelum Pn .


Semoga tesis ini dapat bermanfaat bagi pembaca dan pihakpihak lainnya yang

Recommend Documents