Job Sequencing Problem
Job Sequencing Problem एक Greedy Algorithm based optimization problem है। इसमें हमें Multiple jobs दी जाती हैं, जहाँ हर job के साथ एक deadline और उससे जुड़ा हुआ profit होता है। यह मान लिया जाता है, कि प्रत्येक job को पूरा करने में केवल 1 unit time लगता है।
इस problem का मुख्य उद्देश्य jobs को ऐसे सही sequence (क्रम) में arrange करना है, कि
- कोई भी job अपनी deadline को miss न करे, और
- सभी selected jobs से मिलने वाला total profit maximum हो जाए।
Key Points (मुख्य बिंदु)
- Jobs को सबसे पहले profit के descending order में sort किया जाता है।
- Job को उसकी deadline से पहले वाले latest available time slot में assign किया जाता है।
- यदि किसी job की deadline तक कोई भी time slot खाली न मिले, तो उस job को skip कर दिया जाता है।
- यह problem सभी jobs को schedule करने पर focus नहीं करती, बल्कि maximum profit प्राप्त करने पर ध्यान देती है, इसलिए यह एक optimization problem है।
- Time Complexity : O(n log n)
- Space Complexity : O(d) (जहाँ d = maximum deadline)
Why Job Sequencing is Needed?
मुख्य कारण (Key Reasons)
- Limited Time Constraint : हर job की एक specific deadline होती है। Job Sequencing यह decide करने में मदद करता है कि कौन-सी job पहले execute की जाए ताकि deadline miss न हो।
- Maximizing Profit : अक्सर सभी jobs को करने का समय नहीं होता, इसलिए ऐसी jobs select की जाती हैं जो maximum profit generate करती हों।
- Efficient Resource Utilization : CPU, machine, employee या system time जैसे resources को waste होने से बचाने के लिए सही job sequencing जरूरी होती है।
- Priority-based Decision Making : High-profit या high-priority jobs को पहले complete किया जा सकता है, जिससे overall performance बेहतर होती है।
- Real-Life Scheduling Problems : Job Sequencing का use real-world applications में होता है, जैसे
- CPU Scheduling in Operating System
- Online Booking Systems (IRCTC, Movie Ticket Booking)
- Project Management in task scheduling
- Advertisement Scheduling (Prime Time Ads)
Key Terms Used in Job Sequencing Problem
(मुख्य शब्द)
Term | Explanation |
Job | कोई भी task या work जिसे complete करना होता है, जैसे CPU process या project task। |
Deadline (d) | वह maximum time limit जिसके अंदर job को पूरा करना जरूरी होता है। |
Profit (p) | Job को successfully complete करने पर मिलने वाला लाभ |
Time Slot | Job execution के लिए दिया गया fixed time period। (Standard problem में 1 unit time) |
Sequence (Order) | Jobs को execute करने का क्रम (order) जिससे total profit maximize हो। |
Maximum Deadline | सभी jobs में से सबसे बड़ी deadline, जिससे total time slots तय होते हैं। |
Greedy Algorithm | Algorithm जो हर step पर locally best choice select करता है। |
Optimization Problem | ऐसी problem जिसमें maximum या minimum value प्राप्त करना goal होता है। |
Scheduling | Jobs को समय और deadline के अनुसार arrange करने की process। |
Profit Maximization | Jobs को इस तरह sequence करना कि total profit सबसे ज्यादा मिले। |
Algorithm of Job Sequencing Problem
Step 1: Input लेना
- n jobs की list ली जाती है।
- हर job के साथ दो attributes होते हैं :
- deadline[i]
- profit[i]
Step 2: Sorting
- सभी jobs को profit के descending order में sort किया जाता है।
- Sorting key : profit
Step 3: Maximum Deadline निकालना
- सभी jobs में से maximum deadline (maxDeadline) find की जाती है।
- maxDeadline = total available time slots
Step 4: Slot Array Create करना
- एक array slot[1 … maxDeadline] बनाई जाती है।
- Starting में सभी elements को -1 या false से initialize किया जाता है (जो empty slot को represent करता है)।
Step 5: Job Scheduling
- Sorted jobs को one-by-one traverse किया जाता है।
- हर job के लिए:
- for (j = deadline[i]; j >= 1; j–)
- अगर slot[j] empty हो:
- slot[j] = job[i]
- loop break कर दिया जाता है
- अगर कोई free slot न मिले, तो job discard कर दी जाती है।
Step 6: Profit Calculation
- slot[] array में stored jobs के profits को add किया जाता है।
- यही final maximum profit होता है।
Pseudo Code
Job_Sequencing(jobs, n)
// Step 1: Sort jobs by profit (descending order)
sort jobs by profit decreasing
// Step 2: Find maximum deadline
maxDeadline ← maximum deadline among all jobs
// Step 3: Create slot array
create array slot[1 … maxDeadline]
for i ← 1 to maxDeadline
slot[i] ← -1 // -1 means slot is empty
totalProfit ← 0
// Step 4: Schedule jobs
for i ← 1 to n
for j ← jobs[i].deadline down to 1
if slot[j] = -1 then
slot[j] ← jobs[i]
totalProfit ← totalProfit + jobs[i].profit
break
end if
end for
end for
// Step 5: Result
return totalProfit, slot
Job Sequencing Example (उदाहरण)
Given Jobs Table
| Job | Deadline (d) | Profit (p) |
|---|---|---|
| J1 | 2 | 100 |
| J2 | 1 | 19 |
| J3 | 2 | 27 |
| J4 | 1 | 25 |
| J5 | 3 | 15 |
Step 1: Jobs को Profit के Descending Order में Sort करना
- J1 → Profit = 100
- J3 → Profit = 27
- J4 → Profit = 25
- J2 → Profit = 19
- J5 → Profit = 15
Step 2: Maximum Deadline Find करना
jobs की deadlines : 2, 1, 2, 1, 3
- Maximum Deadline = 3
- Total available time slots = 3
Step 3: Job Scheduling (One by One)
sorted jobs को एक-एक करके schedule करते हैं।
Job J1 (Deadline = 2, Profit = 100)
- Slot 2 Empty → J1 assign
Slot 1 Slot 2 Slot 3
_ J1 _
Job J3 (Deadline = 2, Profit = 27)
- Slot 2 already filled
- Slot 1 Empty → J3 assign
Slot 1 Slot 2 Slot 3
J3 J1 _
Job J4 (Deadline = 1, Profit = 25)
- slot[1] occupied → no slot available
→ job rejected
Job J2 (Deadline = 1, Profit = 19)
- slot[1] occupied → no slot available
→ job rejected
Job J5 (Deadline = 3, Profit = 15)
- Slot 3 Empty → J5 assign
Slot 1 Slot 2 Slot 3
J3 J1 J5
Step 4: Final Job Sequence and Profit
- Scheduled Jobs : J3, J1, J5
- Optimal Job Sequence : J3 → J1 → J5
- Total Profit : 27 + 100 + 15 = 142
Advantages (लाभ)
- Maximum Profit : Greedy Algorithm का use करने से total profit maximum होता है।
- Easy to Understand : Algorithm conceptually easy है: sort → select → assign
- Efficient Use of Resources : Limited CPU time, machines या employees का best utilization होता है।
- Real-Life Applications : CPU Scheduling, Online Booking Systems (IRCTC), Advertisement Scheduling, Project Management आदि में useful।
Disadvantages (सीमाएं)
- Assumes Unit Time Jobs : Standard problem में हर job 1 unit time लेती है, जो सभी real-life jobs पर apply नहीं होता।
- Limited Scope : Complex jobs या dependencies वाले cases में algorithm fail कर सकता है।
- Greedy Limitation : Greedy approach कभी-कभी globally optimal solution नहीं देती।
- Partial Jobs Not Considered : Fractional execution वाले jobs को handle नहीं करता।
