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

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

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

วิธีการแก้

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

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

สมมติกำหนดเวลาของ ith งาน Ji คือ di และผลกำไรที่ได้รับจากงานนี้คือ pi. ดังนั้นทางออกที่ดีที่สุดของอัลกอริทึมนี้คือโซลูชันที่เป็นไปได้และมีกำไรสูงสุด

ดังนั้น $ 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) $

ตัวอย่าง

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

งาน J1 J2 J3 J4 J5
วันกำหนดส่ง 2 1 3 2 1
กำไร 60 100 20 40 20

วิธีการแก้

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

งาน J2 J1 J4 J3 J5
วันกำหนดส่ง 1 2 2 3 1
กำไร 100 60 40 20 20

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

  • ต่อไป, J1 ถูกเลือกเนื่องจากให้ผลกำไรมากกว่าเมื่อเทียบกับ J4.

  • ในนาฬิกาถัดไป J4 ไม่สามารถเลือกได้เนื่องจากกำหนดเวลาสิ้นสุดลงด้วยเหตุนี้ J3 ถูกเลือกเนื่องจากดำเนินการภายในกำหนดเวลา

  • งาน J5 จะถูกยกเลิกเนื่องจากไม่สามารถดำเนินการได้ภายในกำหนดเวลา

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

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