Mathematica for the Liberal Arts

College Algebra Meets the (21^st) Century

Bruce Torrence
						Randolph-Macon College
						Ashland, VA

btorrenc@rmc.edu
						www.rmc.edu/facstaffpages/btorrenc/public_html/

The Scheduling Problem

• A finite list of tasks (Subscript[T, 1]),  (Subscript[T, 2]),  (Subscript[T, 3]),   ...  ,  (Subscript[T, n]), each with an associated processing time.

• An (irreflexive) partial order on the task set, indicating precedence constraints.

The Scheduling Problem

• A finite list of tasks (Subscript[T, 1]),  (Subscript[T, 2]),  (Subscript[T, 3]),   ...  ,  (Subscript[T, n]), each with an associated processing time.

• An (irreflexive) partial order on the task set, indicating precedence constraints.

The Scheduling Problem

• A finite list of tasks (Subscript[T, 1]),  (Subscript[T, 2]),  (Subscript[T, 3]),   ...  ,  (Subscript[T, n]), each with an associated completion time.

• An (irreflexive) partial order on the task set, indicating precedence constraints.

• A finite number of identical parallel processors (Subscript[P, 1]),  (Subscript[P, 2]),   ...  ,  (Subscript[P, m]).

• We assume there is no preemption; once a processor begins work on a task, it will continue until the task is complete.

The Scheduling Problem

The Scheduling Problem

Complexity Results

Complexity Results

Complexity Results

Complexity Results

Complexity Results

Complexity Results

Complexity Results

List Scheduling

7  5  6  3  4  2  1

At any time when a processor is free:

Assign to the lowest numbered free processor the highest priority task that is ready.

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Example - Apply the algorithm

7  5  6  3  4  2  1

Observation: List scheduling can generate any feasible schedule

5  6  1  7  2  3  4

Brute force solution

• Apply the list processing algorithm to each of the n!possible priority lists, thereby generating every feasible schedule.

• Choose an optimal schedule.

Computable Solutions - Two lower bounds on any feasible schedule

Computable Solutions - HLF Algorithms

Generate a priority list as follows:

Computable Solutions - HLF Algorithms

Generate a priority list as follows:
1.  Give highest to priority to the first task on a critical path.

1

Computable Solutions - HLF Algorithms

Generate a priority list as follows:
1.  Give highest to priority to the first task on a critical path.

2.  Delete that task and all associated edges from the digraph.

1

Computable Solutions - HLF Algorithms

Generate a priority list as follows:
1.  Give highest to priority to the first task on a critical path.

2.  Delete that task and all associated edges from the digraph.

3. Give next-highest priority to the first task on a critical path in the new digraph.

1  2

Computable Solutions - HLF Algorithms

Generate a priority list as follows:
1.  Give highest to priority to the first task on a critical path.

2.  Delete that task and all associated edges from the digraph.

3. Give next-highest priority to the first task on a critical path in the new digraph.

4. Go back to step 2.

1  2  3  5  4  6  7

Three Mathematica commands:

times = {5, 10, 8, 6, 12, 10, 15};
edges = {{1, 2}, {1, 3}, {1, 4}, {2, 7}, {3, 7}, {4, 
            7}};

ShowSchedulingDigraph[times, edges, TaskOffset -> {-1, 3}, 
        ImageSize -> 400, 
        Background -> RGBColor[1, 1, 0.8]];

Applying the list-processing algorithm - ShowSchedule

cp = {1, 2, 3, 4, 7, 5, 6};

ShowSchedule[times,  cp,  edges,  2, 
        Background -> RGBColor[1, 1,  .8]];

Brute force exploration - AllScheduleTimes

AllScheduleTimes[times,  edges,  2]

Questions

Try it!  Find a priority list that will generate an optimal schedule (There are 280 correct answers)

ShowSchedulingDigraph[times, edges, TaskOffset -> {-1, 3}, 
        Background -> RGBColor[1, 1,  .8], 
        ImageSize -> 300];

vgpl = veryGoodPriorityList = {1, 4, 2, 3, 7, 6, 5};

pg = prettyGoodPriorityList = {1, 2, 3, 4, 7, 5, 
            6};
ShowSchedule[times,  pg,  edges,  2, 
        Background -> RGBColor[1, 1,  .8]];

Key Features of Mathematica for these investigations

Discussion among groups is encouraged.

Cheating in its most base form is impossible.

Grading is not any harder for the instructor.

Impossible to answer these questions without it - in most cases an optimal schedule will not meet either lower bound.

Conveys a strong sense of the need to find efficient algorithms - each call takes about 40 seconds on the lab computers for a 7-task system.

The End

Oops...		This twit just jumped to the last slide!