2024-02-21

Author

Witek ten Hove

OBP:

Scheduling Theory, Algorithms, and Systems

This comprehensive guide introduces you to the fundamentals of scheduling theory, algorithms, and systems, emphasizing dynamic programming, integer programming, and complex hierarchies within scheduling problems.

Dynamic Programming and Integer Programming

Dynamic programming (DP) is a powerful algorithm design technique that solves optimization problems through recursive decomposition and memorization of intermediate calculations. Integer programming involves finding optimal solutions for discrete variables, making it particularly useful for scheduling problems with integral constraints.

Complexity Hierarchy

Understanding the complexity of scheduling problems helps identify efficient algorithms for specific scenarios. Common scheduling problems lie within the realm of NP-hardness, requiring advanced methods like approximation algorithms, metaheuristics, and exact exponential-time algorithms.

Insert: Eulerian vs Hamiltonian paths

Stochastic Scheduling Problems

In real-world situations, uncertainty exists due to factors like machine failures, random arrival patterns, and varying processing speeds. Stochastic scheduling addresses these challenges by incorporating probabilistic models and statistical analysis.

Python Implementation

To illustrate key concepts, this post includes Python code snippets demonstrating various scheduling algorithms and techniques, such as dynamic programming and integer programming.

For instance, let’s examine a simple weighted interval scheduling problem using dynamic programming. The Python code for the weighted interval scheduling problem using dynamic programming can be applied in project management to optimally allocate resources and improve project efficiency. By implementing this algorithm, project managers can prioritize tasks based on their importance and ensure that critical activities are completed without conflicts.

For example, imagine a software development team working on multiple projects simultaneously. They want to optimize their resource allocation across these projects to meet strict delivery timelines. By applying the weighted interval scheduling algorithm with dynamic programming, they could create a priority list of tasks, taking into account both the urgency and importance of each task. This allows them to make informed decisions about which tasks should receive higher priority during resource allocation, ultimately leading to faster completion times and increased customer satisfaction.

Additionally, this algorithm can help reduce costs by preventing unnecessary duplication of effort and reducing idle time for resources. As a result, organizations can achieve greater productivity and competitiveness in their respective markets.

def weighted_interval_scheduling_with_schedule(requests):
    # Sort requests by finish time to ensure non-overlapping meetings are considered properly
    sorted_requests = sorted(requests, key=lambda r: r['end'])
    
    # Initialize dp array to store tuples of (maximum weight, list of meetings IDs leading to that weight)
    dp = [(0, [])] * (len(sorted_requests) + 1)

    # Helper function to find the latest non-conflicting meeting
    def find_latest_non_conflicting(meeting_index):
        for j in range(meeting_index - 1, -1, -1):
            if sorted_requests[j]['end'] <= sorted_requests[meeting_index]['start']:
                return j + 1
        return 0

    # Fill dp array
    for i in range(1, len(sorted_requests) + 1):
        include_weight = sorted_requests[i-1]['weight']
        include_meetings = [sorted_requests[i-1]['id']]
        
        # Find the latest non-conflicting meeting
        latest_non_conflicting = find_latest_non_conflicting(i-1)
        include_weight += dp[latest_non_conflicting][0]
        include_meetings = dp[latest_non_conflicting][1] + include_meetings
        
        # Choose max of including or excluding the current meeting
        if include_weight > dp[i-1][0]:
            dp[i] = (include_weight, include_meetings)
        else:
            dp[i] = dp[i-1]

    # The last element of dp now contains the maximum weight and the optimal schedule
    max_weight, optimal_schedule = dp[-1]
    print("Maximum weight:", max_weight)
    print("Optimal schedule of meetings:", optimal_schedule)
    return max_weight, optimal_schedule

Business Case: Conference Room Booking Optimization

Background:

A multinational corporation, “GlobalTech,” faces challenges in managing its limited number of conference rooms across various office locations. With a dynamic work environment involving cross-functional teams, the demand for conference rooms varies in terms of importance, team size, and required amenities. The goal is to optimize the allocation of these rooms to ensure that high-priority meetings are accommodated effectively, maximizing overall meeting value to the company.

Decision Problem:

The primary decision problem is how to schedule the use of conference rooms to maximize the total value (or “weight”) of meetings held within a given week, taking into account that meetings have different priorities (weights), durations, and specific start and end times. This problem involves deciding which meetings to approve and schedule in the limited available conference room space to achieve the highest cumulative priority score.

Input Variables:

Requests: A list of meeting requests, each with:
- id: A unique identifier for the meeting.
- start: The requested start time of the meeting.
- end: The requested end time of the meeting.
- weight: The priority or value of the meeting to the organization, which could factor in the importance of the meeting’s purpose, the seniority of participants, or the strategic value of the meeting outcomes.

Solution Method Using Dynamic Programming:

The weighted interval scheduling problem is solved using dynamic programming to ensure that GlobalTech can find the optimal combination of meetings that maximizes the total value of meetings held, while ensuring no two selected meetings overlap in time. The dynamic programming approach involves sorting meetings by their end times, then iteratively building up a solution by considering, for each meeting, whether including it leads to a higher total value than excluding it, given the meetings already considered.

Code Application:

The provided Python function, weighted_interval_scheduling, represents an algorithm to solve this optimization problem. It sorts the meetings by their priority (weight) and then uses dynamic programming to find the optimal subset of meetings that maximizes the total weight without overlaps.

Real-Life Application:

Consider GlobalTech has the following meeting requests for a particular conference room:

Strategic Planning (id: 1, start: 9 AM, end: 11 AM, weight: 50)
Product Launch Review (id: 2, start: 10 AM, end: 12 PM, weight: 40)
Team Building Workshop (id: 3, start: 1 PM, end: 3 PM, weight: 30)
Quarterly Financial Review (id: 4, start: 2 PM, end: 4 PM, weight: 45)

Using the provided code, GlobalTech can input these meetings as requests and determine the optimal schedule that maximizes the total value of meetings hosted in the conference room.

requests = [
    {'id': 1, 'start': 9, 'end': 11, 'weight': 50},
    {'id': 2, 'start': 10, 'end': 12, 'weight': 40},
    {'id': 3, 'start': 13, 'end': 15, 'weight': 30},
    {'id': 4, 'start': 14, 'end': 16, 'weight': 45}
]

weighted_interval_scheduling_with_schedule(requests)

Maximum weight: 95
Optimal schedule of meetings: [1, 4]

(95, [1, 4])

Managerial Perspective:

From a managerial standpoint, this approach enables GlobalTech to make data-driven decisions about allocating scarce resources (conference rooms) in a way that maximizes the strategic value delivered to the company. It considers the complex interplay between meeting times, durations, and their relative importance, providing a clear, optimized schedule that supports the company’s operational and strategic goals. This method also demonstrates to stakeholders the company’s commitment to efficiency and strategic focus, using advanced problem-solving techniques to address everyday operational challenges.

References:

References for Python code:

Elaborations

Dynamic Programming Applied to Scheduling Theory

Dynamic programming stands out as a powerful methodology for addressing scheduling problems by decomposing complex challenges into manageable subproblems. This approach ensures the efficient computation of optimal solutions, exemplified by solving the weighted interval scheduling problem. Through dynamic programming, one can optimize the total weight of non-overlapping intervals, showcasing the technique’s utility in formulating and solving scheduling issues.

Dynamic programming is one of several strategies for polynomial time algorithms. Others are:

Divide and conquer. Eg. mergesort.

def merge_sort(arr):
    if len(arr) > 1:
        # Finding the mid of the array
        mid = len(arr) // 2
        
        # Dividing the array elements into 2 halves
        L = arr[:mid]
        R = arr[mid:]
        print(f"divided array: L:{L}, R={R}")
        
        # Sorting the first half
        merge_sort(L)
        print("sorting L")
        
        # Sorting the second half
        merge_sort(R)
        print("sorting R")

        i = j = k = 0
        print("setting i, j, k to zero")
        
        # Merge the temp arrays back into arr
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
            print("merging L and R")
        
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
            print("checking L")
        
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
            print("checking L")

# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Given array is", arr)
merge_sort(arr)
print("Sorted array is", arr)

Given array is [12, 11, 13, 5, 6, 7]
divided array: L:[12, 11, 13], R=[5, 6, 7]
divided array: L:[12], R=[11, 13]
sorting L
divided array: L:[11], R=[13]
sorting L
sorting R
setting i, j, k to zero
merging L and R
checking L
sorting R
setting i, j, k to zero
merging L and R
merging L and R
checking L
sorting L
divided array: L:[5], R=[6, 7]
sorting L
divided array: L:[6], R=[7]
sorting L
sorting R
setting i, j, k to zero
merging L and R
checking L
sorting R
setting i, j, k to zero
merging L and R
checking L
checking L
sorting R
setting i, j, k to zero
merging L and R
merging L and R
merging L and R
checking L
checking L
checking L
Sorted array is [5, 6, 7, 11, 12, 13]

Greedy algorithms (local searc)

Complexity Measurement and Its Importance

The complexity of scheduling problems significantly influences the selection and development of algorithms. Time complexity and space complexity are two critical metrics for evaluating the efficiency of scheduling algorithms:

Time Complexity: This metric assesses how the execution time of an algorithm scales with the input size. In scheduling theory, the focus might be on understanding whether an algorithm’s running time increases linearly with the number of tasks or exponentially with the complexity of task dependencies.
Space Complexity: This metric evaluates the amount of memory an algorithm uses in relation to the input size. Analyzing an algorithm’s space complexity involves determining whether it requires additional memory beyond the initial input, which is crucial for scheduling problems where storage efficiency can be as important as computational speed.

import math
import plotly.graph_objects as go
from plotly.subplots import make_subplots

def complexity_example(n):
  f = n * math.log(n) + n**2 * 10**8 + n**3 / 1000
  g = n**3
  return f, g
x = [x for x in range(1000000, 150000000, 100000)]
f = [complexity_example(n)[0] for n in x]
g = [complexity_example(n)[1] for n in x]
f_over_g = [f[i]/g[i] for i in range(0, len(f))]

# Create Plotly figure
fig = make_subplots(specs=[[{"secondary_y": True}]])

# Add traces
fig.add_trace(go.Scatter(x=x, y=f, mode='lines', name='f'),
    secondary_y=False,)
fig.add_trace(go.Scatter(x=x, y=g, mode='lines', name='g'),
    secondary_y=False,)
fig.add_trace(go.Scatter(x=x, y=f_over_g, mode='lines', name='f / g',line=dict(dash='dash')),
    secondary_y=True)

# Add titles and labels
fig.update_layout(title='Complexity',
                  xaxis_title='n',
                  yaxis_title='Value',
                  legend_title='Function')

# Show plot
fig

$f(n)=\mathcal{O}(n^3)$ means that when $n$ is large $f(n)$ scales with $n^3$ or less. Here $f(n)$ can mean the time it takes to compute, or the memory necessary to store all instances.

Formally, $f(n)=\mathcal{O}(g(n))$ if there exists constants $C$ and $n_0$ such that, $\forall \ n > n_0, f(n) \leq Cg(n)$

$f(n)=\mathcal{\Omega}(n^3)$ means that when $n$ is large $f(n)$ scales with $n^3$ or more : $g(n) = \mathcal{O}(f(n))$.

$f(n)=\mathcal{\Theta}(n^3)$ means that when $n$ is large $f(n)$ scales with $n^3$ more or less: $f(n) = \mathcal{O}(g(n))$ and $g(n) = \mathcal{O}(f(n))$.

$f(n)=\mathcal{o}(n^3)$ means that when $n$ is large $f(n)$ grows much slower than $n^3$ or the ratio $f(n) / n^3$ tends to zero as $n$ grows.

Example of a function that grows faster than polynomial, but slower than exponential when $n$ is large.

def complexity_example_one(n):
  if n > 0:
    f = n**math.log(n)
  else:
    f = 0
  g1 = n**2
  g2 = 1.5**(n)
  return f, g1, g2

x = [x for x in range(1, 40, 1)]
f, g1, g2 = zip(*[complexity_example_one(n) for n in x])

# Create Plotly figure
fig = go.Figure()

# Add traces
fig.add_trace(go.Scatter(x=x, y=f, mode='lines', name='f'))
fig.add_trace(go.Scatter(x=x, y=g1, mode='lines', name='g1'))
fig.add_trace(go.Scatter(x=x, y=g2, mode='lines', name='g2'))

# Add titles and labels
fig.update_layout(title='Complexity',
                  xaxis_title='n',
                  yaxis_title='Value - log scale',
                  legend_title='Function',
                  yaxis_type='log',  # Logarithmic scale
                  xaxis_type='linear',)

# Show plot
fig

Theoretical and Practical Implications

The complexity hierarchy of scheduling problems underscores the theoretical and practical challenges in developing effective scheduling solutions. This hierarchy highlights the computational intractability of many scheduling problems, emphasizing the need for sophisticated algorithms capable of handling NP-hard problems.

def calculate_values(n):
    n_squared = n ** 2
    n_cubed = n ** 3
    two_log_n_squared = 2 ** (math.log(n, 2) ** 2)  # Assuming log base 2
    two_to_the_n = 2 ** (n)

    return n_squared, n_cubed, two_log_n_squared, two_to_the_n

# Example usage
n = 4
results = calculate_values(n)

# Generate data
n_values = range(1,18)  # Example: Generate values from 1 to 10
n_squared_values = []
n_cubed_values = []
two_log_n_squared_values = []
two_to_the_n_values = []

for n in n_values:
    results = calculate_values(n)
    n_squared_values.append(results[0])
    n_cubed_values.append(results[1])
    two_log_n_squared_values.append(results[2])
    two_to_the_n_values.append(results[3])

# Create Plotly figure
fig = go.Figure()

# Add traces
fig.add_trace(go.Scatter(x=list(n_values), y=n_squared_values, mode='lines+markers', name='n^2'))
fig.add_trace(go.Scatter(x=list(n_values), y=n_cubed_values, mode='lines+markers', name='n^3'))
fig.add_trace(go.Scatter(x=list(n_values), y=two_log_n_squared_values, mode='lines+markers', name='2^{log(n)^2}'))
fig.add_trace(go.Scatter(x=list(n_values), y=two_to_the_n_values, mode='lines+markers', name=r'2^{n^2}'))

# Add titles and labels
fig.update_layout(title='Complexity examples',
                  xaxis_title='n',
                  yaxis_title='Value',
                  legend_title='Function')

# Show plot
fig

Search Results Contextualized: A review of literature and existing resources reveals various facets of scheduling theory, from time-dependent scheduling, which deals with variable job durations, to the mathematical formulations used to represent and solve scheduling problems. These resources illustrate the breadth of scheduling theory, including its application to optimizing finite sets of operations and the representation of processes in task networks.
Addressing Computational Intractability: The classification of scheduling problems based on complexity provides insights into designing efficient scheduling algorithms. This involves not only understanding the theoretical underpinnings of NP-hard problems but also applying practical techniques for managing precedence constraints and other factors that increase computational complexity.

In conclusion, the complexity hierarchy is a critical consideration in scheduling theory, affecting both the theoretical exploration of scheduling problems and the practical development of algorithms. By leveraging dynamic programming and understanding the nuances of time and space complexity, researchers and practitioners can navigate the challenges posed by NP-hard problems, leading to more effective and efficient scheduling solutions.

References:

Time-Dependent Scheduling: Springer Link - Discusses the intricacies of scheduling problems where job durations are influenced by their start times.
Introduction to Scheduling Theory: NYU Stern - Provides an overview of scheduling theory, emphasizing the development of optimal schedules.
Scheduling Theory Overview: Encyclopedia of Mathematics - A comprehensive examination of scheduling theory as a branch of applied mathematics focused on scheduling problem formulations and solutions.
Scheduling Theory in Practice: ScienceDirect - Describes the process representation in scheduling theory, highlighting task network representations.
Complexity of Scheduling Under Precedence Constraints: JSTOR - Discusses the increased computational complexity introduced by precedence constraints in scheduling problems.
Introduction to Scheduling: Amazon - A resource providing insights into the complexities and methodologies of scheduling, including discussions on space and time complexity.
Computation in Complex Systems (Spring 2022): Complexity Explorer - This course offers an in-depth look into computational models and algorithms used in the analysis of complex systems, with relevance to understanding the computational complexity found in scheduling problems.

To multiply two n-digit numbers using a recursive divide and conquer strategy, you can implement the Karatsuba algorithm. This algorithm is more efficient than the traditional grade-school algorithm for large numbers. It works by breaking down the large numbers into smaller parts, multiplying those parts, and then combining them to get the final result. Here’s a simplified explanation and a Python code example:

Given two n-digit numbers (x) and (y), you can represent them as:

$x =10^{n/2} \cdot a + b$
$y = 10^{n/2} \cdot c + d$

Where (a) and (c) are the first half of the digits of (x) and (y), and (b) and (d) are the second half. The Karatsuba algorithm states that: - $x \cdot y = (10^{n} \cdot ac) + (10^{n/2} \cdot (ad + bc)) + bd$

The clever part is how it reduces the number of multiplications. Instead of calculating (ac), (ad), (bc), and (bd) separately (which would be 4 multiplications), it calculates $ac$, $bd$, and $(a+b) (c+d) - ac - $ (which only requires 3 multiplications).

Here’s how you might implement it in Python:

def karatsuba(x, y):
    # Base case for recursion
    if x < 10 or y < 10:
        return x * y
    
    # Determine the size of the numbers.
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    
    # Split the digit sequences in the middle.
    a, b = divmod(x, 10**m)
    c, d = divmod(y, 10**m)
    
    # 3 calls made to numbers approximately half the size
    # 1. Compute ac
    ac = karatsuba(a, c)
    # 2. Compute bd
    bd = karatsuba(b, d)
    # 3. Compute (a+b) * (c+d) - ac - bd
    ad_plus_bc = karatsuba(a + b, c + d) - ac - bd
    
    # Combine the results using the Karatsuba formula
    return ac * 10**(2*m) + (ad_plus_bc * 10**m) + bd

# Example usage
x = 1234
y = 5678
result = karatsuba(x, y)
print(f"The result of multiplying {x} and {y} is {result}")

This code takes two integers x and y, and recursively applies the Karatsuba algorithm to multiply them. The base case for recursion is when x or y is less than 10, at which point it simply returns the product of x and y. For larger numbers, it splits each number into two halves, recursively computes the products of the parts, and combines those products according to the Karatsuba formula.