3.1 Interval Scheduling🔗

Source code at interval-scheduling.rkt

Interval scheduling is assigning sets of requests to resources. Each resource can process only one request at a time. A request asks to use a resource for a time interval, from a start time to a finish time.

(struct request (start finish) #:transparent)

Two requests are compatible if they can be processed by the same resource. This means that their time intervals do not overlap.

(module+ test

(check-true (compatible? (request 1 2) (request 2 3)))

(check-true (compatible? (request 2 3) (request 1 2)))

(check-false (compatible? (request 1 3) (request 2 4)))

(check-false (compatible? (request 2 4) (request 1 3))))

(define (compatible? request1 request2)

(or

(<= (request-finish request1) (request-start request2))

(<= (request-finish request2) (request-start request1))))

A set of requests is a valid schedule if they can all be processed by a single resource, i.e., the requests are all compatible with each other.

(module+ test

(check-true (valid-schedule? (list (request 2 3) (request 1 2) (request 3 5))))

(check-true (valid-schedule? (list (request 2 3))))

(check-true (valid-schedule? '()))

(check-false (valid-schedule? (list (request 2 4) (request 1 2) (request 3 5)))))

If we sort the requests, we can check successive pairs for compatibility.

(define (all-compatible? sorted-requests)

(or (empty? sorted-requests)

(empty? (rest sorted-requests))

(and (compatible? (first sorted-requests) (second sorted-requests))

(all-compatible? (rest sorted-requests)))))

(define (valid-schedule? requests)

(all-compatible? (sort requests < #:key request-start)))

A basic interval scheduling problem is to find a valid schedule of maximum size from a set of requests.

We’ll show a few different implementations. Here’s some tests that each scheduler will have to pass.

A schedule must be the expected size and must be valid.

(module+ test

(define (check-schedule requests expected-size name)

(with-check-info (('input name))

(check-equal? (length requests) expected-size "length")

(check-true (valid-schedule? requests) "valid"))))

We test the schedulers with empty, single, and multiple requests.

(module+ test

(define (test-scheduling scheduler name)

(with-check-info (('scheduler name))

(check-schedule (scheduler '()) 0 "empty")

(check-schedule (scheduler (list (request 1 2)))

1 "single")

(check-schedule (scheduler (list (request 3 5) (request 2 4) (request 1 3) (request 4 6)))

2 "multiple"))))

The approach is to take the request with the earliest finish time, then drop any incompatible requests. This is repeated for the remaining requests, until we’ve processed all of them.

Our first implementation sorts the requests by finish time. We then use a filter to drop incompatible requests, using a minimum start time. The filter predicate has a side-effect of updating the minimum start time whenever it accepts a request.

(module+ test

(test-scheduling schedule-with-filter "filter"))

(define (schedule-with-filter requests)

(define minimum-start 0)

(define (take-request? request)

(and (>= (request-start request) minimum-start)

(set! minimum-start (request-finish request))))

(filter take-request? (sort requests < #:key request-finish)))

Using a predicate function with a side-effect is maybe not the best solution. We can avoid this by using a procedure that builds the result recursively.

(module+ test

(test-scheduling schedule-by-finish "by finish"))

(define (schedule-by-finish requests)

(define (build-results first-request results)

(if (or (empty? results)

(>= (request-start first-request) (request-finish (first results))))

(cons first-request results)

results))

(define (build-schedule requests results)

(if (empty? requests)

results

(build-schedule (rest requests) (build-results (first requests) results))))

(build-schedule (sort requests < #:key request-finish) '()))

This recursive procedure returns the requests in descending order. This is because we prepend to a results list, so later requests appear earlier in the results. If we want the results in ascending order, we can use a similar approach by taking the request with the latest start time, instead of earliest finish time. This means we sort the requests descending by start time, so the recursive procedure builds results in ascending order.

(module+ test

(test-scheduling schedule-by-start "by start"))

(define (schedule-by-start requests)

(define (build-results first-request results)

(if (or (empty? results)

(<= (request-finish first-request) (request-start (first results))))

(cons first-request results)

results))

(define (build-schedule requests results)

(if (empty? requests)

results

(build-schedule (rest requests) (build-results (first requests) results))))

(build-schedule (sort requests > #:key request-start) '()))

The two recursive procedures may select different requests, but they will both select the same number of requests.