Planning and Scheduling

List Processing
We are given

a collection of tasks,
an order requirement directed graph,
a priority list imposing an order on the tasks
the number of processors

Goals:

minimize the completion time
minimize the time any processor is idle
find the minimum number of processors needed to finish the job

Example: House construction

dig a hole A
pour concrete B
erect frame C
outside walls D
roof E
plumbing F
interior walls G
electric wiring H
windows/doors I
painting/carpets J

Priority list (dictated by labor cost, availability, weather, etc): F H J I D E A C G B

Note: this problem is also NP hard (just like the Hamilton circuit)

A task is ready at a particular time, if all its predecessors in the requirement digraph have been completed.
e.g. you can't do the wiring until the interior walls are done.

List Processing Algorithm

repeat until all tasks are done:
assign the first ready and not yet assigned task on the priority list to the lowest numbered processor

Example:

Priority list: T₈, T₇,T₆,T₅,T₄,T₃,T₂,T₁,
Schedule the tasks on two processors and find the completion time.

Example: same requirement digraph, different priority list: T₁,T₂,T₃,T₄,T₅,T₆,T₇,T₈
Schedule the tasks on two processors and find the completion time.

Critical Path Schedules

sofar the priorities list was given in the beginning

Question: Is there a systematic way of choosing a priorities list that yields better results when processing a list?

use the critical path scheduling algorithm to
generate a priorities list
schedule tasks on a single processor

Critical Path Scheduling Algorithm

repeat until no more vertices are left in the directed graph:

find task that heads a critical path (break tie by choosing the task with the lower number)
place task next on the priorities list
remove task from the directed graph

Example: Given the directed graph

use the critical path scheduling algorithm to find a priority list

use the list processing algorithm to schedule the tasks on

2 processors. What is the minimum completion time?

3 processors. What is the minimum completion time?

Given independent tasks of various time lengths and some processors
Schedule the tasks on the processors, so as to minimize total completion time

Decreasing Time List Processing Algorithm

sort the tasks in order of decreasing time lengths to get a priority list
apply the list processing algorithm

Example: Process tasks with time lengths 10, ,9, 8, 7, 5, 4 on two processors

Example: Given 8 tasks with a total time length of 72 minutes. Distributed onto 3 processors, what is the minimum completion time?

Bin Packing

Task: Given objects with weights w₁, w₂, w₃,... , w_n
Find the minimum number of bins with weight capacity w, so that all objects can be packed into the bins and never exceed the weight capacity for any bin.

Applications:

packing for a move
planning a CD
seating people in a restaurant
allocating resources in fixed unit amounts

This is NP complete.

Heuristics:

Next Fit (NF), Next Fit Decreasing (NFD)
First Fit (FF), First Fit Decreasing (FFD)
Worst Fit (WF), Worst Fit Decreasing (WFD)

Next Fit:

see if next object fits into the current bin

if yes -- put it in
if no -- move to next bin and put it in there and make that bin the current one

Comment: this potentially leaves a lot of space in the earlier bins, if smaller objects come later in the list. The earlier bins cannot be accessed any more. But the algorithm is fast and doesn't use much computing space..

Example: Pack items of these sizes:
6, 3, 4, 5, 2, 3, 4, 2, 6, 1
into bins of size 8.

First Fit:

fit the next object into the first among the currently used bin where it fits.

Worst Fit:

Fit the next object into the currently used and not yet filled bin with the most open space.

Decreasing Time Heuristics:

sort the object list by decreasing weight and apply the previous heuristics.

Comments:

decreasing time heuristics may give smaller number of bins, but are more time consuming, because of the sorting. This also needs more computing space, because data is stored while it is sorted.
first fit and worst fit also may give a smaller number of bins, but are more time consuming, because of the look back to previous bins
NF, FF, WF: don't need to know all weights in advance.

Rescheduling Conflicts via Coloring

represent conflicts via graphs: vertices are objects, an edges represents a conflicts between two objects.

Example: schedule committee meetings for members of a state legislature.
vertices: committees:

Agriculture A, Commerce C, Consumer Affairs CA, Education E, Forests F, Health H, Justice J, Labor L, Rules R

               edge: there is a legislator who is a member of two committees, who would have a time conflict if both committees held meetings
                at the same time.
                These conflicts are given by a table:

	A	C	CA	E	F	H	J	L	R
A		x	x			x
C	x		x	x	x
CA	x	x					x		x
E		x			x	x
F		x		x		x	x
H	x			x	x			x
J			x		x			x	x
L						x	x		x
R			x				x	x

Draw the graph represented by this table.

Vertex Coloring: color the vertices so that no two vertices sharing an edge are colored with the same color.
(different color - different meeting time)
The chromatic number is the least number of colors needed to do the vertex coloring.
(least number of colors - least number of different meeting times needed so that no legislator has a time conflict)