Operational Research Notes > Operational Research Techniques Notes

This is an extract of our **Or202.1 Operational Research Techniques Course Notes** document, which
we sell as part of our **Operational Research Techniques Notes** collection written by the top tier of
LSE students.

* The following is a more accessble plain text extract of the PDF sample above, taken from our Operational Research Techniques Notes.
Due to the challenges of extracting text from PDFs, it will have odd formatting:
*

Lecture 2: Introduction to Flowshop Scheduling 15 October 2010

Topics

* Introduction to Flow Shop Scheduling

* N Jobs to be Processed Through Two Machines in a Static Flowshop

* Johnson's Algorithm

* N Jobs to be Processed Through 3 Machines in a Static Flowshop

Introduction to Flow Shop Scheduling

* Production Scheduling = Used when making decision to find a good sequence of activities to determine how tasks should be processed

* Heuristic = No set method or approach is available so we try to find a suitable one in a logical way

* Makespan = The total elapsed time of the project

* The quicker the makespan the better

* Job-Shop (Process) = Consists of a number of machines, the jobs that have to be processed through these machines, and a definition of any restrictions there may be on the sequencing of some or all of the jobs on particular machines

* Our objective in this part of the course is to minimise the total elapsed time Definitions

* Formal statement and solution of a sequencing problem is:

? If is the value, cost or utility of performing task A first followed by B, and is the value, cost or utility of performing task B first followed by A, and if is preferable to , then the ordering "A first then B" is chosen, else "B first then A"

* Static Problems = All jobs arrive simultaneously, all immediately available to work

? More is known about static problems

* Dynamic Problems = Jobs arrive continuously

* Flowshop = A job-shop in which all jobs follow the same path from one machine to another

* Multiply Optimal = When there are two or more optimal job sequences that generate an equally good schedule

N Jobs to be Processed Through Two Machines in a Static Flowshop

* When there are only two jobs, it is easy to solve by drawing the only two possible Gantt Charts and choosing the one with the smaller makespan Johnson's Algorithm

* We use Johnson's Algorithm when the number of jobs is greater than 2 in a 2-machine flowshop and

* Let the two machines be called and and let the n jobs have processing times

* The times can be either exact or expected

* Lower bound on the project makespan is: Johnson's Algorithm Steps

* Step (1)

* Define the list of jobs which are initially candidates for sequencing: this will be all n jobs

* Step (2)

* Select the smallest processing time on either machine from all the jobs not yet sequenced. Initially this will mean selecting the smallest of all n+n times. If there is a tie simply choose one of these best times at random. Go to step (3)

* Step (3)

* If this least processing time is , then job r should be placed in the earliest available position in the sequence. Initially this would mean placing it first. If it is then job r should be placed in the last available position in the sequence. Initially this would mean sequencing this job in the last position Go to step (4)

* Step (4)

* If all jobs have now been sequenced then stop. Otherwise return to Step (1)

N Jobs to be Processed Through 3 Machines in a Static Flowshop

* There is no optimal solution to the general case

* Only trial and error or complete enumeration can find the optimal solution in most cases

* However Burns and Rooker proved a theorem that worked in some cases

Burns and Rooker Theorem

* For a flowshop with 3 machines A, B and C, Johnson's Algorithm can be modified and used to produce a guaranteed optimal schedule if any one of the following three conditions is satisfied: for all

*

for all

*

*

* The conditions suggest that the middle machine times are relatively small compared to the other two

* If one of the conditions is satisfied then we can create a pseudo machines so that the processing times of machine 1 are the sums of the times on A and B and machine 2 is the sum of B and C

* Lower bound on the makespan is the maximum of:

*

*

*

Course Notes Page 1

Key Points

* Job-shops

* 2 jobs through 2 machines - static flowshop

* Johnson's Algorithm

* Burns and Rooker Theorem Definitions

* Dynamic Problems = Jobs arrive continuously

* Flowshop = A job-shop in which all jobs follow the same path from one machine to another

* Heuristic = No set method or approach is available so we try to find a suitable one in a logical way

* Job-Shop (Process) = Consists of a number of machines, the jobs that have to be processed through these machines, and a definition of any restrictions there may be on the sequencing of some or all of the jobs on particular machines

* Makespan = The total elapsed time of the project

* Multiply Optimal = When there are two or more optimal job sequences that generate an equally good schedule

* Production Scheduling = Used when making decision to find a good sequence of activities to determine how tasks should be processed

* Static Problems = All jobs arrive simultaneously, all immediately available to work Formula

* Lower bound on the project makespan is:

Lecture 3: Replacement Theory 22 October 2010

Topics

* Introduction to Replacement Theory

* Replacement Strategies for Individual Systems or Items That Wear

* Replacement Strategies for Groups of Items that Fail

Key Points

* Non-stochastic vs. stochastic problems

* Replacement strategies for individual systems

* Individual replacement

* Planned group replacement

* Preventative maintenance

Introduction to Replacement Theory

* Two types of decision to be made on replacement:

* Non-Stochastic Problem:

* When a major single item of equipment wears out and we must balance rising maintenance costs against the alternative to replace the item

* Stochastic Problem:

* When either individual items or groups of items are liable to fail suddenly and need to be replaced. Preventative maintenance may be carried out, also

* Unplanned group replacement

* The renewal process

* Steady-state age distribution Definitions

*

*

Replacement Strategies for Individual Systems or Items that Wear

* These are non-stochastic problems

* Calculate the net annual cost for each replacement frequency i.e. every period, every 2 periods etc.

* Calculate the average net annual cost

* We want to minimise the average net annual cost

* Example of finding the optimal replacement strategy for individual items that wear

*

= The cost of an individual replacement

*

= The cost of group replacement per unit

*

= the expected replacement cost per period of this planned group replacement strategy

Replacement Strategies for Groups of Items that Fail

* i.e. set of all fridges in a hospital

* There are two problems to consider:

* To predict when failures are likely to occur

* To choose a replacement strategy

* We consider four specific replacement strategies:

* Individual Replacement = Replace each item individually at the end of the time period

* Group Replacement = Replace the whole group periodically, with failures also being replaced as they arise

* Preventative Maintenance = Maintenance to hopefully make the item as good as new

* Unplanned Group Replacement = Replace the whole group when the first failure is observed (particularly when the group size is quite small)

* In all replacement strategies, inspections must be carried out regularly

* So that replacements can take place at the end of that inspection period

* Individual Replacement = Replace each item individually at the end of the time period

Definitions and Notation

* The life of an individual item is a random variable

*

* Survivor Probability (Reliability Function) = Probability of no failure up to and including time period j

* Average cost per unit time spread over the n intervals =

* Group Replacement = Replace the whole group periodically, with failures also being replaced as they arise

* Marginal cost of individual failures in an extra (n+1) interval =

* Planned group replacement = Replace the whole group every n intervals of time

* Preventative Maintenance = Maintenance to hopefully make the item as good as new

* Renewal Process = If the individual units are replaced when they fail by units with identical and independent failure time distributions

* Replacement Policy = Choice between replacing items before or after they fail

* Survivor Probability (Reliability Function) = Probability of no failure up to and including time period j

* Unplanned Group Replacement = Replace the whole group when the first failure is observed (particularly when the group size is quite small) Formulae

*

***

**

The Renewal Process

* Renewal Process = If the individual units are replaced when they fail by units with identical and independent failure time distributions items, we can forecast the expected number of units that have to be replaced in

* Starting with period j

* There is a pattern for this:*

*

* Expected cost of this strategy = L =

* Expected cost per unit =

*

* Expected number of units to be replaced per unit time =

* The renewal process can be illustrated in a failure tree

* Probability of the first failure being in period

* The expected (average) cost of replacement per unit time

*

? There are many different forms for a failure tree Steady-State Age Distribution

* In the long run (steady state), as

,

will tend towards a constant value

*

* On average a proportion of the population will be replaced each period at that time

* We let

so that

* We can then say how many items are expected to be in their first period in the steady state, in their second period and so on (defining the expected age distribution):

* In their first period -> N units

? In their second period ->

* In their third period ->

Replacement Policies and Strategies

* Replacement Policy = Choice between replacing items before or after they fail

* It is often worthwhile to replace items before they fail with brand new items if group replacement is cheaper than individual replacement Two possible replacement strategies:

Course Notes Page 2

*Buy the full version of these notes or essay plans and more in our Operational Research Techniques Notes.*