DAA - ลำดับงานพร้อมกำหนดเวลา

คำชี้แจงปัญหา

ในปัญหาการจัดลำดับงานมีวัตถุประสงค์เพื่อค้นหาลำดับงานซึ่งจะเสร็จสิ้นภายในกำหนดเวลาและให้ผลกำไรสูงสุด

วิธีการแก้

ให้เราพิจารณาชุดของ nงานที่กำหนดซึ่งเกี่ยวข้องกับกำหนดเวลาและผลกำไรจะได้รับหากงานเสร็จสิ้นตามกำหนดเวลา งานเหล่านี้จำเป็นต้องสั่งซื้อในลักษณะที่มีกำไรสูงสุด

อาจเกิดขึ้นได้ว่างานทั้งหมดที่กำหนดอาจไม่เสร็จภายในกำหนด

สมมติกำหนดเวลาของ i^th งาน J_i คือ d_i และผลกำไรที่ได้รับจากงานนี้คือ p_i. ดังนั้นทางออกที่ดีที่สุดของอัลกอริทึมนี้คือโซลูชันที่เป็นไปได้และมีกำไรสูงสุด

ดังนั้น $ D (i)> 0 $ สำหรับ $ 1 \ leqslant i \ leqslant n $

ในขั้นต้นงานเหล่านี้จะเรียงลำดับตามผลกำไรเช่น $ p_ {1} \ geqslant p_ {2} \ geqslant p_ {3} \ geqslant \: ... \: \ geqslant p_ {n} $

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

การวิเคราะห์

ในอัลกอริทึมนี้เราใช้สองลูปหนึ่งอยู่ภายในอีกอันหนึ่ง ดังนั้นความซับซ้อนของอัลกอริทึมนี้คือ $ O (n ^ 2) $

ตัวอย่าง

ให้เราพิจารณาชุดของงานที่กำหนดดังแสดงในตารางต่อไปนี้ เราต้องหาลำดับของงานซึ่งจะแล้วเสร็จภายในกำหนดเวลาและจะให้ผลกำไรสูงสุด แต่ละงานเกี่ยวข้องกับกำหนดเวลาและผลกำไร

งาน	J₁	J₂	J₃	J₄	J₅
วันกำหนดส่ง	2	1	3	2	1
กำไร	60	100	20	40	20

วิธีการแก้

เพื่อแก้ปัญหานี้งานที่กำหนดจะถูกจัดเรียงตามผลกำไรจากมากไปหาน้อย ดังนั้นหลังจากการเรียงลำดับงานจะถูกเรียงลำดับตามที่แสดงในตารางต่อไปนี้

งาน	J₂	J₁	J₄	J₃	J₅
วันกำหนดส่ง	1	2	2	3	1
กำไร	100	60	40	20	20

จากชุดของงานนี้ก่อนอื่นเราเลือก J₂เนื่องจากสามารถดำเนินการให้เสร็จสิ้นภายในกำหนดเวลาและสร้างผลกำไรสูงสุด

ต่อไป, J₁ ถูกเลือกเนื่องจากให้ผลกำไรมากกว่าเมื่อเทียบกับ J₄.
ในนาฬิกาถัดไป J₄ ไม่สามารถเลือกได้เนื่องจากกำหนดเวลาสิ้นสุดลงด้วยเหตุนี้ J₃ ถูกเลือกเนื่องจากดำเนินการภายในกำหนดเวลา
งาน J₅ จะถูกยกเลิกเนื่องจากไม่สามารถดำเนินการได้ภายในกำหนดเวลา

ดังนั้นวิธีแก้ปัญหาคือลำดับของงาน (J₂, J₁, J₃) ซึ่งจะดำเนินการภายในกำหนดเวลาและให้ผลกำไรสูงสุด

กำไรรวมของลำดับนี้คือ 100 + 60 + 20 = 180.