Decision 1

An activity is a job or process that forms part of an overall project. An activity that begins at event i and finishes at event j is referred to as activity (i, j).

On a precedence network, an activity is represented by an arc.

An algorithm is a sequence of precise instructions to solve a problem. Algorithms can be expressed as a sequence of steps, as flowcharts, or using pseudo-code.

In queuing situations it is necessary to simulate the times at which new items (people, cars, items on a production line, etc.) join the queue. There are two ways to address this: arrival times, and inter-arrival times.

Using arrival times, you consider a unit of time of fixed length (say 10 seconds) and use observed data to estimate a probability of a new arrival to the queue during that time. For exampl, this would be 0.5 if you recorded 5 arrivals in a 100 second period, i.e. in every 10 second period there is a 0.5 probability of a new arrival and a 0.5 probability that there is no new arrival. Shortening the arrival time to, say, 1 second, and using a probability of 0.05 for a new arrival and 0.95 for no new arrival could improve the accuracy of the simulation.

The problem with using arrival times in simulations is that as you reduce the arrival time, the number of random numbers that you will need to generate increases proportionally, so that to run a simulation over a given time period requires considerably more calculations.

An advantage of using arrival times is that it is straightforward to work out how long the queue is at any time.

This is the problem of fitting a number of items of the same width and depth but different heights into a rack or bin.The bin is assumed to be the same width and depth as the items. The problem is to decide how best to fit the items into the bins, using as few bins as possible.

There are many applications of this problem. Pages 9 and 10 of the textbook look at the ‘Plumbing problem’, the ‘Ferry loading problem’ and the ‘Disc storage problem’.

There are three heuristic algorithms you should know which address the bin-packing problem.They are the Full-bin algorithm, the First-Fit algorithm and the First-Fit decreasing algorithm.

A bipartite graph is one in which the vertices fall into two sets, and each edge has a vertex from one set at one end, and a vertex from the other set at the other end.

This is a sorting algorithm.

To sort a list into increasing order (i.e. with the smallest item at the start of the list) the bubble sort works as follows:

• On the first pass, the first number in the list is compared with the second, and whichever is the smaller assumes the first position. The second is then compared with the third and the smaller is placed in the second position, and so on through the list. At the end of the first pass the largest number must be at the bottom of the list.
• For the second pass, the process is repeated, but excluding the last number, and on the third pass the last two numbers are excluded.
• Passes continue in this way until a pass with no swaps occurs. The list is then sorted.

A similar process can be used to produce a decreasing list.

A cascade chart is a diagram, with time on the horizontal axis, which shows how activities are arranged chronologically (in terms of time) with relation to one another. Moving activities around on a cascade chart, within the time limits allowed by their floats, enables resource levelling to be carried out.

A complete graph is a simple graph in which every pair of vertices is connected by an edge.

For some algorithms, doubling the size of the problem will result in doubling the number of steps required to solve it. Such algorithms are described as having linear complexity. For other algorithms, doubling the size of the problem will result in quadrupling the number of steps required to solve it. Such algorithms are described as having quadratic complexity.

Some problems can be solved by a variety of different algorithms. An algorithm with linear complexity will be far more efficient than one with quadratic complexity, resulting in a faster solution. This can be especially important when solving very large-scale problems on a computer. A more efficient algorithm requires less memory and less processor time.

A graph is connected if a path exists between every pair of vertices.

The constraints of a linear programming problem are linear inequalities that restrict the values of the variables in the problem. These inequalities are produced in the formulation process and relate to any limited availability of resources.

In order to simulate the occurrence of events using random numbers, it is necessary to specify which random numbers correspond to which event, according to the probability of each event. To simulate the probabilities exactly, it must be possible to allocate random numbers to events in exact proportion to the probabilities of occurrence of the events. To do this, it may be necessary to reject some of the random numbers, i.e. not all of the possible random numbers will be allocated to an event.

Crashing a network is using extra resources to "speed up" activities, in order to reduce the minimum time to complete a project. The extra resources used will almost certainly result in increased costs, but sometimes the time saved may be worth more than the cost of speeding activities.

Of course, there is no point (initally at least) in speeding up non-critical activities as these already have spare time. Once some critical activities have been speeded up, some of the activities that were previously non-critical may become critical, making it worthwhile to speed them up too.

A critical activity is an activity with no float. Any delay to a critical activity will result in a delay for the project as a whole. A critical activity must lie on a critical path.

If an activity (i, j) is critical, the latest event time of event j, minus the earliest event time of event i, minus the duration of the activity, must equal 0.

A critical path is a route through a precedence network on which all of the activities are critical activities.

There may be more than one critical path, but all critical paths must follow a continuous route from the start node to the finish node.

This is the process of analysing a project, to enable the best use to be made of time and other resources.

A cycle is a closed path (i.e. the end of the last edge is the start of the first, and no vertices are repeated except that the final vertex is the same as the first).

Decision variables are the variables whose optimum values you are trying to determine through the use of linear programming. For example, they could be levels of production to maximise income.

In D1 you will only be expected to deal with situations involving two decision variables. It is usual to denote these variables as x and y. This is the first part of the formulation process. Their possible values can then be shown on a graph.

The degree (or order) of a vertex is the number of ends of edges connecting into it.

A digraph is a graph in which at least one edge has a direction associated with it.

This is an algorithm for finding the shortest route between two nodes on a network.

•Label the starting node S with a permanent label of 0.
•For all nodes that can be directly reached from S, give temporary labels equal to their direct distance from S.
•Select the node with the smallest temporary label and make its label permanent.
•Put a temporary label on each node that can be reached directly from the node which has just received a permanent label. The temporary label is the sum of the permanent label and the direct distance from it. If there is an existing temporary label at a node, it should be replaced only if the new sum is smaller.
•Select the minimum temporary label and make it permanent.
•Continue this procedure until the destination node has a permanent label.
•To find the shortest path, trace back from the destination, including any arc whose length is equal to the difference between the permanent labels at either end of the arc.

This is a tabular representation of a network, in which each element represents the weight of the arc between two nodes on the network.

The earliest event time (EET) for an event is the earliest time at which it is possible for the activities leading from an event node on a precedence network to start.

EETs are calculated by performing a "forwards pass" through the precedence network, from the start node to the finish node.

An edge (arc) is a line connecting two vertices (nodes) on a graph.

An event ocuurs when an activity can start, or when the whole project is complete. Events are represented by the nodes on a precedence network.

This is a node (junction) on a precedence network. Activities meet at event nodes: some activities finish and other activities (which are dependent on the completion of those activities leading into the event node) start.

For a problem involving two variables, the feasible region is a region on an x, y graph where all of the constraints in a linear programming problem are satisfied. All possible solutions to the linear programming problem lie in this region.

This is the event node that occurs on the completion of the entire project.

The early event time and the late event time of the finish node must both equal the minimum possible duration of the project.

This is a heuristic greedy algorithm for the bin-packing problem.

Taking the boxes in the order listed, place the next box to be packed in the first available slot that can take the box.

This is a heuristic greedy algorithm for the bin-packing problem.

• Reorder the boxes in order of decreasing size
• Apply the first-fit algorithm to this reordered list.

The float on an activity is the amount of time by which it may be delayed without affecting the overall time for completion of the project.

The total float for an activity may be divided into independent float and interfering float.

A flowchart is a diagrammatic representation of the sequence of steps in an algorithm. A flowchart expresses an algorithm in a clear and economical way.

This is the process of translating a practical problem into the mathematical notation of a linear programming problem. It is a particular example of mathematical modelling.

This is a heuristic algorithm for the bin-packing problem.

Look for combinations of boxes to fill the bins. Pack these boxes. For the remainder, plack the next box to be packed in the first available slot that can take that box.

A graph is a set of vertices, linked in some way with a set of edges.

An algorithm in which at each stage the immediately best option is chosen without being concerned about the long-term consequences of the choice.

Kruskal's algorithm and Prim's algorithm are greedy algorithms. Both of these algorithms always lead to the optimal solution, but some greedy algorithms, such as the first-fit algorithm and the first-fit decreasing algorithm, are heuristic and may not give the optimal solution.

A cycle which visits every vertex. Since a cycle is a path, each vertex is visited once and only once.

A heuristic algorithm is one which will usually find a good, if not the best, solution to a problem. An efficient heuristic algorithm will consistently find a good solution to the problem it addresses.

The full-bin algorithm, first-fit algorithm and first-fit decreasing algorithms are all examples of heuristic algorithms for the bin-packing problem.

An incidence matrix is a way of representing a graph on a matrix. Rows and columns correspond to vertices, and the entries in the matrix correspond to the number of edges from one vertex to another.

This is spare time associated with a particular activity.

An activity can be delayed by an amount up to its independent float without delaying the start of any other activity, or the overall completion time of the project.

For an activity (i, j), the independent float is found by: earliest event time of event j - latest event time of event i - duration of activity (or zero if this calculation gives a negative answer).

This is a sorting algorithm.

The insertion sort is similar to how you might arrange a hand of cards. Numbers are taken from the unsorted list one at a time, in sequence. They are then inserted into their correct positions in the new list.

In many practical situations, the decision variables we are trying to calculate in a linear programming type problem can only take integer values. For instance, these variables might represent the numbers of each of two types of item which are to be produced.

Such problems are actually more difficult to deal with that linear programming problems with continuous variables. However, the integer programming solution is usually close to the linear programming solution, so a useful method is to check the integer solutions that lie close to the linear programming solution. If the linear programming solution is an integer, it is the optimal solution, so no further points need to be checked.

The inter-arrival time is the time between successive arrivals in a queue. Inter-arrival times are also referred to as arrival intervals.

Inter-arrival times are used in queuing simulations as follows:

• From observed data of when new arrivals appear in a queue, construct a table of arrival intervals and the percentage of occasions on which those intervals occurred.
• The percentages can then be converted to probabilities, which can be simulated using random numbers.
• The accuracy of a simulation may be improved by having more inter-arrival times.

The disadvantage of using inter-arrival times is that it can be difficult to see the length of the queue at a given time.

The advantage is that it requires fewer calculations to simulate a given time period than using arrival times.

This is a sorting algorithm (sometimes called the selection with interchange sort).

• Find the smallest number in the list and swap it with the first number.
• Find the next smallest number in the list and swap it with the second number.
• Continue in this manner until the list is sorted.

This is spare time associated two or more activities. If an activity is delayed by an amount up to its interfering float, it may delay the other activities with which it shares interfering float, but it will not delay the overall completion time of the project.

Interfering float = total float - independent float

Two graphs are isomorphic if one can be stretched, twisted or otherwise distorted into the other.

When graphs are isomorphic, it is possible to label their vertices so that the linkage between corresponding vertices is the same.

This is an algorithm for finding the minimal spanning tree of a network.

• Select the shortest arc of the network.
• At each subsequent stage, select from those arcs which have not yet been selected, the shortes arc which does not link nodes between which a path has already been created. If at any stage there is a choice of shortest arcs, choose arbitrarily between them.
• Continue until all nodes are connected.

The latest event time (LET) for an event is the latest time at which it is possible for activities leading into that event node on a precedence network to finish, without delaying the whole project.

LETs are calculated by performing a "backwards pass" through the precedence network, from the finish node to the start node.

The formulation and solution of a problem in which the variables in the problem are subject to only linear constraints. The solution will give the optimum values for the decision variables in the problem. These optimum values will result in the best possible value of the objective function.

An arc whose beginning and end both link into the same vertex.

This is the mean number of things (people, cars, objects on a conveyor belt etc.) in the queue.
This is calculated as:

This is the mean of the times for which each member of the queue spends in the queue. It is calculated as:

A minimal spanning tree, or minimum connector, is a tree that connects all of the nodes of a network together using the minimum total arc length.

A minimal spanning tree can be found using Prim's algorithm or Kruskal's algorithm.

Monte Carlo is famous for its casinos and for games of chance. Monte Carlo methods are so called because they involve the use of a random device such as a coin, die or computer random number generator to imitate chance happenings in the real world.

A network is a weighted graph. A weighted graph has a number (the weight) associated with each arc.

In a linear programming problem, the solution will always involve minimising or maximising the value of some quantity. This is called the objective. For example, the objective might be to maximise profit or production, or to minimise cost. The objective function is an equation that relates the value of the objective quantity to the decision variables in the problem.

A path is a trail in which no vertex is repeated.

A planar graph is one that can be drawn without any edges crossing.

A network drawn to show how the activities in a project are dependent upon one another. Activities are represented by arcs in the network.

This is an algorithm for finding the minimal spanning tree of a network.

• Select an arbitrary node, then connect it to the nearest node.
• Now connect the nearest node that is not already connected, to those already in the solution.
• Repeat until all nodes have been connected.

This algorithm can also be applied to a network in table form, which means that it can easily be adapted for use by computer.

This is the overall task to be analysed using critical path analysis. A project is made up of a number of different activities.

This is a cross between English and computer code, which enables an algorithm to be expressed in a clear and economical way. Pseudo code can be easily converted into a computer program.

This is a cross between English and computer code, which enables an algorithm to be expressed in a clear and economical way. Pseudo code can be easily converted into a computer program.

The queuing discipline is the rule by which a queue operates. For example, in a post office there might be a single queue from which customers go to the first available window, but in a supermarket there would probably be a separate queue for each checkout.

This is a sorting algorithm.

• First split the list into two sub-lists, one containing those numbers less than or equal to the first number in the list (called the pivot), the other containing those greater than it.
• Place the pivot number between the two sub-lists (do not reorder the sub-lists).
• Repeat the process on sub-lists containing two or more numbers until there are no such sub-lists. The list is then sorted.

A random device is a device that generates a random outcome. It produces outcomes which all have the same probability - these are uniformly distributed random variables.

For example, tossing an unbiased coin produces the outcomes "heads" or "tails" with equal probabilities of 0.5; rolling a fair die produces the outcomes 1, 2, 3, 4, 5 or 6, with equal probabilities of . Calculator random number generators usually generate 1000 possible random numbers, from 0.000 to 0.999, each with probability . Computer programs such as Excel can generate as many random numbers as you would ever need.

These are constraints that do not border the feasible region. This means that they do not affect the solution of the problem.

This is a diagram with time on its horizontal axis and the quantity of a particular resource on its vertical axis (e.g. number of workers, number of cement mixers).

Resource histograms for a project may be produced using a cascade chart.

This is the process of juggling the activities on the cascade chart to minimise the maximum quantity of a given resource that is needed for a project, and even-up the use of a given resource throughout the duration of the project. The resource concerned could be workers, tractors etc.

This process is called resource levelling because the resource histogram for the project will appear less "spiky", i.e. more level, once the levelling process has taken place.

Resources are the things needed to carry out a project. They include time, money, people and machinery.

The is the percentage of time that the server of a queue is busy.
This is calculated as:

This is a sorting algorithm.

• First pass: compare the first two numbers and swap if necessary to place in ascending order.
• Second pass: compare the second and third numbers and swap if necessary. If a swap has taken place, then compare the first and second numbers and swap if necessary.
• Third pass: compare the third and fourth numbers and swap if necessary. If a swap has taken place, then compare the second and third numbers and swap if necessary. If a swap has taken place, then compare the first and second numbers and swap if necessary.
• Continue passes in the same way. In each pass, the pass ends when a swap is not required.

A graph in which there are no loops and in which there is no more than one edge connecting any pair of vertices.

Simulation is the imitation of the operation of a system.

The solution to a linear programming problem is the set of values of the variables that maximise or minimise (depending on the problem) the value of the objective function while still satisfying all of the constraints. It will always lie in the feasible region.

A sorting algorithm sorts items into order. You need to be familiar with the bubble sort, the shuttle sort, the insertion sort and the quick sort.

This is the event node that represents the event that occurs at the beginning of the whole project. The earliest event time and latest event time for the start node must both equal zero.

A trail is a walk in which no edge is repeated.

A tree is a simple connected graph with no cycles.

Random numbers used in simulations are examples of uniformly distributed random variables. Each number should be equally likely to occur, so if you selected a set of random numbers and plotted their frequencies, their frequencies should tend towards being equal, as the number of random numbers selected increases. Their frequency distribution will be flat, or uniform.

A vertex (node) is a point on a graph that is connected to other vertices by edges (arcs).

A walk is a sequence of edges in which the end of each edge (except the last) is the beginning of the next.

A numerical value (often a distance) associated with an arc on a network.