Dengan latar belakang yang disediakan oleh bagian sebelumnya, kita dapat merumuskan penjadualan jalur kritis matematis.
Kami akan menyajikan algoritma atau set instruksi untuk penjadualan jalur kritis dengan asumsi jaringan kegiatan proyek-on-cabang.
Kita juga mengasumsikan bahwa semua precedences adalah dari selesai-untuk-memulai alam, sehingga aktivitas berhasil tidak dapat dimulai sebelum selesainya suatu kegiatan sebelumnya. Dalam bagian selanjutnya, kami menyajikan algoritma yang sebanding untuk kegiatan-on-node representasi dengan jenis beberapa didahulukan.
Misalkan bahwa jaringan proyek kami memiliki n +1 node, kejadian awal adalah 0 dan acara terakhir yang n. Biarkan waktu di mana peristiwa terjadi menjadi simpul x 1, x 2 ,...., x n, masing-masing. Awal proyek pada x 0 akan didefinisikan sebagai waktu 0. Nodal acara kali harus konsisten dengan jangka waktu kegiatan, sehingga penerus simpul kegiatan saatnya acara harus lebih besar dari acara simpul waktu kegiatan yang pendahulunya ditambah durasinya. Untuk kegiatan didefinisikan sebagai dimulai dari acara i dan berakhir di acara j, hubungan ini dapat dinyatakan sebagai kendala ketidaksetaraan, x j x i + D ij ij dimana D adalah durasi aktivitas (i, j). Ini ekspresi yang sama dapat ditulis untuk setiap kegiatan dan harus berlaku dalam setiap Jadual layak. Matematis, maka, masalah jalur kritis penjadualan adalah untuk meminimalkan waktu penyelesaian proyek (x n) tunduk pada kendala bahwa setiap acara simpul penyelesaian tidak dapat terjadi sampai setiap kegiatan pendahulunya telah selesai:
Memperkecil
(10.1)
Memperkecil
(10.1)
tunduk pada
Ini adalah masalah pemrograman linear karena nilai tujuan untuk diminimalkan dan setiap kendala merupakan persamaan linier.
Daripada memecahkan masalah penjadualan jalur kritis dengan algoritma linear programming (seperti metode Simplex), teknik yang lebih efisien yang tersedia yang mengambil keuntungan dari struktur jaringan dari masalah. Metode-metode solusi yang sangat efisien sehubungan dengan perhitungan yang diperlukan, sehingga jaringan yang sangat besar dapat diobati bahkan dengan komputer pribadi. Metode ini juga memberikan beberapa informasi yang sangat berguna tentang Jadual kegiatan yang mungkin. Program dapat menghitung waktu mulai paling awal dan terbaru yang mungkin untuk setiap kegiatan yang konsisten dengan menyelesaikan proyek dalam waktu sesingkat mungkin. Perhitungan ini adalah kepentingan tertentu untuk kegiatan yang tidak pada jalur kritis (atau jalan), karena kegiatan ini mungkin sedikit tertunda atau re-diJadualkan dari waktu ke waktu sebagai manajer keinginan tanpa menunda keseluruhan proyek.
Sebuah proses solusi efisien untuk penjadualan jalur kritis berdasarkan label simpul ditunjukkan pada Tabel 10-1. Tiga algoritma muncul dalam tabel. Acara penomoran angka algoritma node (atau peristiwa) dari proyek tersebut bahwa peristiwa awal memiliki angka yang lebih rendah daripada acara akhir untuk setiap kegiatan. Secara teknis, algoritma ini menyelesaikan semacam "topologi" dari kegiatan. Simpul memulai proyek diberikan angka 0. Selama kegiatan proyek memenuhi kondisi untuk suatu aktivitas jaringan-on-cabang, jenis sistem penomoran selalu mungkin. Beberapa paket perangkat lunak untuk penjadualan jalur kritis tidak memiliki algoritma penomoran diprogram, sehingga perencana konstruksi proyek harus memastikan bahwa penomoran yang tepat dilakukan.
TABEL 10-1 Algoritma Penjadualan Kritis (Kegiatan-on-Cabang Representasi)
|
Acara Penomoran Algoritma
|
Langkah 1: Berikan 0 acara nomor awal.
Langkah 2: Berikan nomor berikutnya untuk setiap peristiwa yang tak terhitung peristiwa pendahulunya masing-masing sudah nomor. Ulangi Langkah 2 sampai semua peristiwa nomor. |
Acara Terlama Waktu Algoritma
|
Langkah 1: Misalkan E (0) = 0.
Langkah 2: Untuk j = 1,2,3 ,..., n (dimana n adalah acara terakhir), biarkan E (j) = maksimum {E (i) + D ij} dimana maksimum dihitung atas semua kegiatan (i, j) yang memiliki j sebagai acara berakhir. |
Acara Terbaru Waktu Algoritma
|
Langkah 1: Misalkan L (n) sama dengan waktu penyelesaian yang dibutuhkan proyek.
Catatan: L (n) harus sama dengan atau melebihi E (n). Langkah 2: Untuk i = n-1, n-2, ..., 0, biarkan L (i) = minimal {L (j) - D ij} mana minimum dihitung atas semua kegiatan (i, j) yang telah saya sebagai peristiwa awal. |
Algoritma acara sedini menghitung waktu sedini mungkin, E (i), di mana setiap peristiwa, saya, dalam jaringan dapat terjadi. Kali acara Terlama dihitung sebagai maksimum dari waktu mulai paling awal ditambah jangka waktu kegiatan untuk setiap kegiatan sesaat sebelum peristiwa. Waktu mulai paling awal untuk setiap kegiatan (i, j) adalah sama dengan waktu sedini mungkin untuk E acara sebelumnya (i):
(10.2)
(10.2)
(10.3)
Kegiatan diidentifikasi dalam algoritma ini dengan node pendahulu (atau peristiwa) i dan node penggantinya j. Algoritma hanya memerlukan bahwa setiap acara di jaringan harus diperiksa di awal gilirannya dengan dimulainya proyek (node 0).
Algoritma acara waktu terbaru menghitung waktu mungkin terbaru, L (j), di mana setiap j acara dalam jaringan dapat terjadi, mengingat waktu penyelesaian yang diinginkan dari proyek, L (n) untuk acara terakhir n. Biasanya, waktu penyelesaian yang diinginkan akan sama dengan waktu penyelesaian sedini mungkin, sehingga E (n) = L (n) untuk node akhir n. 
Prosedur untuk menemukan waktu acara terbaru adalah analog dengan bahwa untuk waktu acara awal, kecuali bahwa prosedur dimulai dengan acara final dan bekerja mundur melalui kegiatan proyek. Dengan demikian, algoritma acara waktu awal sering disebut lulus maju melalui jaringan, sedangkan algoritma waktu acara terbaru adalah melewati mundur melalui jaringan. Waktu selesai terakhir konsisten dengan penyelesaian proyek dalam kerangka waktu yang diinginkan dari L (n) untuk setiap kegiatan (i, j) adalah sama dengan L waktu terakhir mungkin (j) untuk acara berikutnya: 
(10.5)
Awal awal dan waktu selesai acara terbaru untuk masing-masing potongan informasi yang berguna dalam mengembangkan Jadual proyek. Acara yang sama awal dan terbaru kali, E (i) = L (i), terletak pada jalur kritis atau path. Sebuah kegiatan (i, j) adalah kegiatan kritis jika memenuhi semua kondisi berikut:
(10.6) 
Oleh karena itu, kegiatan antara peristiwa penting juga di jalur kritis selama waktu mulai paling awal kegiatan yang sama dengan waktu mulai terbaru, ES (i, j) = LS (i, j). Untuk menghindari menunda proyek, semua kegiatan pada jalur kritis harus dimulai sesegera mungkin, sehingga setiap kegiatan kritis (i, j) harus diJadualkan untuk mulai pada waktu mulai sedini mungkin, E (i).
Contoh 10-2: perhitungan jalur kritis penjadualan
Perhatikan jaringan yang ditunjukkan pada Gambar 10-4 di mana memulai proyek diberi nomor 0. Kemudian, satu-satunya peristiwa yang masing-masing bernomor pendahulunya adalah penerus kegiatan A, sehingga ia menerima nomor 1. Setelah ini, satu-satunya peristiwa yang masing-masing bernomor pendahulunya adalah penerus dua kegiatan B dan C, sehingga ia menerima nomor 2. Angka kejadian lain yang dihasilkan dari algoritma juga ditunjukkan pada gambar. Untuk jaringan ini proyek sederhana, setiap tahap dalam proses penomoran hanya menemukan satu peristiwa yang mungkin ke nomor setiap saat. Dengan lebih dari satu peristiwa layak untuk nomor, pilihan yang ke nomor berikutnya adalah sewenang-wenang. Misalnya, jika kegiatan C tidak ada dalam proyek untuk Gambar 10-4, acara penerus untuk kegiatan A atau kegiatan B bisa menjadi nomor 1.
Gambar 10-4 Jaringan Sembilan-Kegiatan Proyek
Setelah nomor node ditetapkan, alat bantu yang baik untuk penjadualan manual untuk menggambar persegi panjang kecil di dekat setiap node dengan dua entri mungkin. Sisi kiri akan berisi waktu awal peristiwa itu bisa terjadi, sedangkan sisi kanan akan berisi waktu terakhir peristiwa itu bisa terjadi tanpa menunda keseluruhan proyek. Gambar 10-5 mengilustrasikan sebuah kotak khas.
TABEL 10-2 Precedence Hubungan dan Durasi untuk Contoh Proyek Sembilan Aktivitas
| |||
Aktivitas
|
Keterangan
|
Pendahulu
|
Jangka waktu
|
Sebuah
B C D E F G H Aku |
Situs kliring
Penghapusan pohon Umum penggalian Grading area umum Penggalian parit untuk Menempatkan bekisting dan penguatan untuk beton Instalasi saluran pembuangan baris Instalasi utilitas lain Menuangkan beton |
---
--- Sebuah Sebuah B, C B, C D, E D, E F, G |
4
3 8 7 9 12 2 5 6 |
Langkah 1
 |
E (0) = 0
|
Langkah 2
| |
j = 1
|
E (1) = Max {E (0) + D 01} = Max {0 + 4} = 4
|
j = 2
|
E (2) = Max {E (0) + D 02, E (1) + D = 12} {Max 0 + 3; 4 + 8} = 12
|
j = 3
|
E (3) = Max {E (1) + D 13; E (2) + D = 23} {4 + Max 7; 12 + 9} = 21
|
j = 4
|
E (4) = Max {E (2) + D 24; E (3) + 34} = D Max {12 + 12; 21 + 2} = 24
|
j = 5
|
E (5) = Max {E (3) + D 35; E (4) + 45} = D Max {21 + 5; 24 + 6} = 30
|
Jadi, waktu minimum yang diperlukan untuk menyelesaikan proyek tersebut adalah 30 karena E (5) = 30. Dalam hal ini, setiap peristiwa memiliki paling banyak dua pendahulunya.
Untuk "lulus mundur," perhitungan waktu kejadian terakhir adalah:
Langkah 1
|
L (5) = E (5) = 30
|
Langkah 2
| |
j = 4
|
L (4) = Min {L (5) - D 45} = Min {30-6} = 24
|
j = 3
|
L (3) = Min {L (5) - D 35; L (4) - D 34} = Min {30 -5; 24-2} = 22
|
j = 2
|
L (2) = Min {L (4) - D 24; L (3) - D 23} = Min {24-12; 22-9} = 12
|
j = 1
|
L (1) = Min {L (3) - D 13; L (2) - D 12} = Min {22-7; 12-8} = 4
|
j = 0
|
L (0) = Min {L (2) - D 02; L (1) - D 01} = Min {12-3; 4 - 4} = 0
|
Dalam contoh ini, E (0) = L (0), E (1) = L (1), E (2) = L (2), E (4) = L (4), dan E (5) = L (5). Akibatnya, semua node tetapi simpul 3 berada di jalur kritis. Kegiatan pada jalur kritis mencakup A (0,1), C (1,2), F (2,4) dan saya (4,5) seperti yang ditunjukkan pada Tabel 10-3.
TABEL 10-3 Identifikasi Kegiatan di Jalur Kritis untuk Proyek Sembilan-Kegiatan
| ||||
Aktivitas
|
Jangka waktu
D ij |
Terlama waktu mulai
E (i) = ES (i, j) |
Latest selesai waktu
L (j) = LF (i, j) |
Latest waktu mulai
LS (i, j) |
A (0,1)
B (0,2) C (1,2) D (1,3) E (2,3) F (2,4) G (3,4) H (3,5) Aku (4,5) |
4
3 8 7 9 12 2 5 6 |
0 *
0 4 * 4 12 12 * 21 21 24 |
4 *
12 12 * 22 22 24 * 24 30 30 * |
0
9 4 15 13 12 22 25 24 |
* Aktivitas pada jalur kritis karena E (i) + D ij = L (j).
