Real-World Problem in Discrete Mathematics：Task Scheduling with Deadlines

Problem Statement

A set of tasks, each with a profit and deadline, must be scheduled on a single resource (like a processor).

Each task takes one unit of time, and the goal is to maximize profit by scheduling as many tasks as possible within their deadlines.

Example

You are given the following tasks:

Task Deadline Profit
A 2 100
B 1 19
C 2 27
D 1 25
E 3 15

Objective: Maximize profit while ensuring that tasks are completed within their deadlines.

Solution

The problem can be solved using a greedy algorithm:

  1. Sort tasks in descending order of profit.
  2. Assign each task to the latest available time slot before its deadline (if available).
  3. Skip the task if no slot is available.

Python Implementation

Here’s the $Python$ code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import matplotlib.pyplot as plt

# Task class to hold task details
class Task:
    def __init__(self, name, deadline, profit):
        self.name = name
        self.deadline = deadline
        self.profit = profit

# Task scheduling function
def job_scheduling(tasks):
    # Sort tasks by profit in descending order
    tasks = sorted(tasks, key=lambda x: x.profit, reverse=True)
    max_deadline = max(task.deadline for task in tasks)
    schedule = [None] * max_deadline  # Initialize schedule
    total_profit = 0
    
    for task in tasks:
        # Try to schedule the task at the latest available time slot before its deadline
        for t in range(min(task.deadline, max_deadline) - 1, -1, -1):
            if schedule[t] is None:
                schedule[t] = task
                total_profit += task.profit
                break
    
    return schedule, total_profit

# Input tasks
tasks = [
    Task("A", 2, 100),
    Task("B", 1, 19),
    Task("C", 2, 27),
    Task("D", 1, 25),
    Task("E", 3, 15)
]

# Schedule tasks
schedule, total_profit = job_scheduling(tasks)

# Extract data for visualization
scheduled_tasks = [task.name if task else None for task in schedule]
profits = [task.profit if task else 0 for task in schedule]

# Print results
print("Scheduled Tasks:", scheduled_tasks)
print("Total Profit:", total_profit)

# Visualization
fig, ax = plt.subplots(figsize=(10, 5))

# Bar chart for profit
ax.bar(range(1, len(profits) + 1), profits, color='skyblue', label='Profit')

# Annotations for task names
for i, task in enumerate(schedule):
    if task:
        ax.text(i + 1, profits[i] + 2, task.name, ha='center', fontsize=12, color='black')

# Graph settings
ax.set_title("Scheduled Tasks and Their Profits", fontsize=14)
ax.set_xlabel("Time Slot", fontsize=12)
ax.set_ylabel("Profit", fontsize=12)
ax.set_xticks(range(1, len(profits) + 1))
ax.set_xticklabels([f"Slot {i}" for i in range(1, len(profits) + 1)])
ax.legend()
plt.grid(alpha=0.3)
plt.show()

Explanation of Code

  1. Class Definition:
    A Task class is defined to store details about each task, including its name, deadline, and profit.

  2. Sorting Tasks:
    Tasks are sorted in descending order of profit to maximize the total profit.

  3. Scheduling:
    For each task, the algorithm attempts to schedule it in the latest available time slot before its deadline.

  4. Visualization:
    A bar chart is used to represent the profits for the scheduled tasks, with annotations for task names.

Results and Visualization

For the given example:

  • Scheduled Tasks: ['A', 'C', 'E']
  • Total Profit: 142

The graph displays the profits earned from scheduled tasks across time slots, with task names annotated above each bar:

  1. Slot 1: Task A (Profit = 100)
  2. Slot 2: Task C (Profit = 27)
  3. Slot 3: Task E (Profit = 15)

This approach ensures that the total profit is maximized while adhering to the deadlines.