DAA - डेडलाइन के साथ जॉब सीक्वेंसिंग
समस्या का विवरण
जॉब सीक्वेंसिंग समस्या में, उद्देश्य नौकरियों का एक क्रम खोजना है, जो उनकी समय सीमा के भीतर पूरा हो जाता है और अधिकतम लाभ देता है।
समाधान
आइए हम इस पर विचार करें nदी गई नौकरियां, जो समय सीमा के साथ जुड़ी हुई हैं और लाभ अर्जित किया जाता है, यदि कोई नौकरी अपनी समय सीमा से पूरी हो जाती है। इन नौकरियों को इस तरह से आदेशित करने की आवश्यकता है कि अधिकतम लाभ हो।
ऐसा हो सकता है कि दिए गए सभी काम उनकी समय सीमा के भीतर पूरे न हों।
मान लें, की समय सीमा ith काम Ji है di और इस नौकरी से प्राप्त लाभ है pi। इसलिए, इस एल्गोरिथ्म का इष्टतम समाधान अधिकतम लाभ के साथ एक संभव समाधान है।
इस प्रकार, $ डी (i)> $ 1 के लिए $ 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विश्लेषण
इस एल्गोरिथ्म में, हम दो छोरों का उपयोग कर रहे हैं, एक दूसरे के भीतर है। इसलिए, इस एल्गोरिथ्म की जटिलता $ हे (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।