The Mathematics of Scheduling
Scheduling is arranging or planning events to occur at a certain time. It serves as an answer to questions such as "How long does it take to build a house?" The answer to this simple question is actually quite complicated due to the many factors that must be considered. For instance, there are obvious factors, such as the size of the house, or the materials needed; however, there are more complicated factors, like coordinating people and equipment to accomplish the goal in a timely way. This leads to the study of Combinatorial Scheduling.
Basic Definitions
•Processors- These are the "workers" that will complete the tasks
•Tasks - This is an indivisible unit of work
•Processing Time - The time needed for a processor to complete a given task, X
Basic Assumptions
For simplicity, we assume the following three assumptions
•Versatility - Any processor can execute an task
•Uniformity - The processing time for a task is the same regardless of which processor is executing the task
•Perseverance - Once a processor starts a task, it will complete the task without interruption
Precedence Relations
If you cannot complete a task Y, without first completing a task X, (X→Y) this is referred to as a Precedence Relation
However, two tasks are said to be Independent if neither X nor Y have a precedence relation.
Another note about precedence relations is that they exhibit transitivity. If (X→Y) and (Y→Z), then (X→Z). Lastly, we cannot have a set of precedence relations that form a cycle. In other words, we cannot have (X→Y) and (Y→Z) and (Z→X).
