Penjadwalan Online dengan Zona Terlarang

Abstract

Online scheduling can be seen as scheduling with incomplate information, namely processing time are unknown, at certain points (times) decision have to be made without knowing the complate instance or depending on the way how new infor- mation becomes known. In various manufacturing and computing contexts there may be a certain period in each time interval, during which processing may con- tinue but may not be initiated. Suppose the n jobs to be scheduled by J1, · · · , Jn. Let pi be the processing time of Ji. Furthermore, we shall assume from now on that pi 1, 8i. Partition time into a set of abutting intervals I = {I1, I2, · · · , Is} with I1 = [0, 1], I2 = [1, 2], · · · , Is = [s1, s]. Each Ij includes a corresponding forbidden zones Fj Ij8j, dimana F1 = ( 1 2 , 1], F2 = ( 3 2, 2], · · · , Fs = (s1 2, s]. We call the intervals Ij\Fj allowed zones. Forbidden zones represent time inter- vals during which a job cannot be started, but can be processed. In this thesis, the author examine the problems of online scheduling in the presence of such forbid- den zones and investigate adaptation of the online bin packing algorithm there is first fit, next fit and harmonics algorithm for problems of online scheduling with forbidden zones at time interval of I and the forbidden zone of F.

Penjadwalan on-line dapat dilihat sebagai penjadwalan dengan informasi yang belum lengkap, yakni waktu proses (run times) pada saat pekerjaan tiba belum diketahui, atau pada titik-titik (waktu) tertentu keputusan dibuat tanpa menge- tahui kejadian lengkap, atau tergantung bagaimana cara informasi baru dike- tahui. Dalam konteks manufaktur dan komputasi berbagai kemungkinan adanya periode tertentu dalam setiap interval waktu, di mana pengolahan dapat terus berlangsung tetapi tidak dapat dimulai. Misalkan n pekerjaan dijadwalkan oleh J1, · · · , Jn, dan misalkan pi waktu proses pada Ji. Untuk selanjutnya asumsikan pi 1, 8i. Waktu dipartisi kedalam himpunan interval I = {I1, I2, · · · , Is} dengan I1 = [0, 1], I2 = [1, 2], · · · , Is = [s1, s]. Setiap Ij memuat sebuah koresponden zona terlarang Fj Ij 8j, dimana F1 = ( 1 2 , 1], F2 = ( 3 2 , 2], · · · , Fs = (s1 2, s]. Interval Ij\Fj disebut daerah yang diizinkan. Zona terlarang merepresentasikan interval waktu dimana suatu pekerjaan tidak dapat dimulai tetapi dapat diproses. Dalam tesis ini penulis memeriksa masalah penjadwalan online dengan adanya zona ter- larang dan menyelidiki adaptasi algoritma online bin packing yaitu first fit, next fit dan em harmonic untuk persoalan penjadwalan online dengan zona terlarang pada interval waktu I dan zona terlarang F tersebut.