jk"Vªh; izkS|ksfxdh laLFkku jk;iqj
NATIONAL INSTITUE OF TECHNOLOGY RAIPUR
(Institute of National Importance)
G.E. Road, Raipur – 492010 (C.G.)
E-mail: director@nitrr.ac.in, Website: www.nitrr.ac.in
Semester - VII
1 Department proposing the Mechanical Engineering
course
2 Course Title Mechanical Lab-9
3 Periods per week 2
4 Credits 1
5 Course Code ME107401ME
6 Status (Core/Elective) Essential Program Requirement
7 Frequency of Offer Once in a year
8 List of Experiments:
1. Determination of the optimal cost and nature of solution for the given L.P.P. (In
solver or any high-level programming language)
2. To find the optimum solution for a given transportation problem. (In solver or any
programming language)
3. To plot the Operating Characteristic (OC) curve for a single attribute plan for a
given case and to compare the theoretical OC with actual OC
4. To draw the P- chart for the fraction defectives and check the control of the process
for a given case.
5. To determine the forecasted demand by two different approaches for a given data
set and compare the effectiveness of each approach.
6. To plot the tracking signal for the given demand data set.
7. Design and develop a program to minimize the make span time of the given flow
shop problem by different heuristics
8. To draw the total cost curve and find the optimal strategy for a given problem
considering quantity discount model and marginal quantity.
9. Evaluate the takt time using palmer, CDS and compare the result with branch and
bound method.
10. Find out the line efficiency of the given assembly line balancing problem.
9 Course Outcome
After the completion of this course, the students will be able:
1. To develop programming skills on solvers/ MS excel for solving LPP problems.
2. To understand the concept of Operating Characteristic (OC), Control Charts and
able to draw the curves/Charts for controlled and uncontrolled processes.
3. To develop a program for forecasting the demand by different methods,
compare their effectiveness and to understand the concept of tracking signal.
4. Understand operations plan on production lines and shop floors to model and
solve the problem for optimization of decision variable.
5. Understand and applying heuristics and exact solution techniques for solving
production problems on high level language programming platforms.
Correlation between Course Outcomes (COs) and Program Outcomes (POs)
PO-1 PO-2 PO-3 PO-4 PO-5 PO-6 PO-7 PO-8 PO-9 PO- PO- PO-
10 11 12
CO-1 3 3 3 2 2 2 1 0 3 0 1 2
CO-2 3 3 2 2 1 1 2 0 2 0 2 2
CO-3 3 3 1 2 3 1 1 0 2 0 2 2
CO-4 3 3 3 3 2 2 2 0 2 0 3 1
CO-5 3 3 3 3 3 2 1 0 2 0 2 2
Experiment 1
Aim: Determination of the optimal cost and nature of solution for the given L.P.P. (In solver or any high-level
programming language)
Software required: Excel solver/ Python
Theory: Linear programming uses a mathematical model to describe the problem of concern. The adjective
linear means that all the mathematical functions in this model are required to be linear functions. The word
programming does not refer here to computer programming; rather, it is essentially a synonym for planning.
Thus, linear programming involves the planning of activities to obtain an optimal result, i.e., a result that reaches
the specified goal best (according to the mathematical model) among all feasible alternatives.
Sample problem:
A corporation plans on building a maximum of 11 new stores in a large city. They will build these stores in one of three
sizes for each location – a convenience store (open 24 hours), standard store, and an expanded services store. The
convenience store requires $4.125 million to build and 30 employees to operate. The standard store requires $8.25
million to build and 15 employees to operate. The expanded-services store requires $12.375 million to build and 45
employees to operate. The corporation can dedicate $82.5 million in construction capital, and 300 employees to staff
the stores. On the average, the convenience store nets $1.2 million annually, the standard store nets $2 million annually,
and the expanded services store nets $2.6 million.
Procedure:
Excel solver-
1. Assign the variables:
𝑥1 = number of convenience stores
𝑥2 = number of standard stores
𝑥3 = number of expanded services stores
2. Write the constraints
a. 𝑥1 + 𝑥2 + 𝑥3 ≤ 11
b. 4.125𝑥1 + 8.25𝑥2 + 12.375𝑥3 ≤ 82.5
c. 30𝑥1 + 15𝑥2 + 45𝑥3 ≤ 300
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
3. Write the objective function
𝑀𝑎𝑥 𝑵 = 1.2𝑥3 + 2𝑥2 + 2.6𝑥3
4. Type in variable assignments at the top of the spreadsheet and assign decision variable cells. Decision
variable cells: D6, F6, and H6.
5. Construct table from data in problem. How you set up the table is a matter of personal preference. Not
in table: the constraint which shows the sum is less than or equal to eleven.
6. Formulas in cells:
7. Click on Tools. If you do not see Solver then click on Add-Ins and select Solver. Now click on Tools
again and select Solver.
8. Target cell: Maximize cell. To enter it, just click on that cell. Equal to Max Changing Cells: Decision
variable cells D6, F6, H6. Subject to the constraints: Click on Add. Click on Cell Reference and then
click in D15, then click on Constraint and then click in F15. Be sure the test listed between them is <=.
Now click on Options
9. Make sure Assume Linear Model and Assume Non-Negative boxes are checked, then click OK. Back at
the Solver, click Solve. It should yield the solution. Click on Keep solution.
Results:
TORA solver
TORA is a prominent software package for linear programming and its extensions. It is simple and has an easy
to use interface for first time users. Almost all the work that has been done manually in the previous lab
reports can be done on TORA. TORA is a powerful software developed by Hamady A. Taha, the author of the
Operations Research book. Needless to say that there are plenty of other software in the market as well. Some
of the major are CPLEX, LINDO and the most powerful of all Excel. Spreadsheet based solvers are becoming
increasingly popular for linear programming problems and its extensions.
This is the main TORA screen, where we choose the type of problem to be solved. Click Linear Programming.
Now Click on ‘GO TO INPUT SCREEN’ to start a problem from scratch, Click ‘Select Existing File’ if you
have already saved the data and want to reopen it.
Now enter the data as seen in the image above & then click on ‘SOLVE menu’, a screen pops up, saying ‘Do
you wish to save data’, Choose the desired option
Experiment 2
Aim:- Solution of Transportation problem using MS-Excel.
Problem:-Solve the following transportation problem where cell entries are unitcost.
Distributi Distributi Distributi Distributi Distributi Availa
on Center on Center on Center on Center on Center ble
1 2 3 4 5
Plant 1 68 35 4 74 15 18
Plant 2 57 88 91 3 8 17
Plant 3 91 60 75 45 60 19
Plant 4 52 53 24 7 82 13
Plant 5 51 18 82 13 7 15
Requir 16 18 20 14 14
ed
Tool Used:-Microsoft Excel 2016
Result:- Minimum transportation cost is 2,202 rs.
Procedure:-
1. Open MSEXCEL and add solver as explained before.
2. Make original table on sheet and then after leaving some space copy it below.
3. In front of table write ‘Total’. Under this column use’=SUM’ command against
each row and add element of row horizontally.
4. Do the same operation vertically also.
5. Delete the element of table except supply and demand.
6. Make objective cell i.e. maximization or minimization of cost and use
‘=SUMPRODUCT’ command taking one array of zero cost matrix and another from
original cost matrix.
7. Go to data and choose ‘SOLVER’.
8. Set objective cell as maximization or minimization of cost value and set max or
min.
9. Select zero cost matrix as changing variable cell.
10. Add constraint as ‘total’ in step 3 & 4 is equal to respective supply and demand.
11. Check make unconstraint variable nonnegative and select solving method
‘Simplex LP’.
12. Click on solve and generate answer sheet,
13. Interpret the found result.
Step 1:-
Step 2:-
Step 3:-
Step 4:-
Step 5:-
Experiment 3
AIM: To plot the operating characteristic curve for a single sampling attributes plan of a given lot
of board pins, and to compare the actual O.C curve with theoretical O.C curve.
APPARATUS REQUIRED:
1. Lot of Copper pins –150 nos.
2. Lot of Steel pins –50 nos.
3. Tray – 1 no.
THEORY : Acceptance sampling is a major component of quality control and in this inspection is
performed on a shipment or lot of incoming materials / products. Samplings aretaken from this
shipment and certain quality characteristics of the units are inspected. After this inspection, a certain
decision is made concerning the lot. Usually, the decision is either toaccept or reject the lot.
Acceptance sampling plan can be divided into attributes sampling plan and variable
sampling plan. In attributes sampling, a unit is classified as conforming or non-conforming based on
whether it meets established specification or not. In variable sampling only one quality characteristic
of a unit is observed or measured. The advantages of sampling inspection are as follows.
1. The cost and time required for sampling inspection is quite less as compared to
100%inspection.
2. Problem of inspection fatigue which occurs in 100 % inspection is eliminated.
3. Smaller inspection staff is necessary.
There are three important types of sampling plans:
1. single sampling plan.
2. Double sampling plan.
3. Multiple sampling plan.
SINGLE SAMPLING PLAN: A single sampling plan is a procedure in which a sample drawn
from a lot and inspected. If the no. of non-conforming or defective units are less than or equal to a
specified limit (i.e., acceptance number), the lot is accepted. Otherwise the lot is rejected. Three
parameters are needed to define a single sampling plan.
1 – Number of units (N) or lot size.
2 – Number of units (n) to be drawn from the lot (sample size).
3 – Acceptance number (c) which is the maximum number of defective units allowed in
asample.
If a single sampling is specified as N= 3000, n=25, c = 2. It means that from a lot sizeof
3000, a random sample of 25 units is drawn and inspected. If the number of defective unitsin the
sample is less than or equal to 2, the lot is accepted otherwise the sample is rejected.
O. C. CURVE: O. C. Curve is an evaluation tool that shows the probability of accepting alimit
submitted for inspection for a range of fraction defective values. It also displays the
discriminatory power of a sampling plan. In other words, it can be used to compare the
probability of accepting a lot for various sampling plans.
The probability of acceptance of a lot is the probability that the no. of defectives in a sample
is equal to or less than the acceptance no. for the sampling plan. there are three distributions that can
be used for finding the probability of acceptance hypergeometric, binomial and the Poisson
distribution. When its assumptions can be met, thePoisson distribution is preferable because of the
ease of calculation.
Probability of acceptance that the no of defective in a sample is equal to or less than
acceptance number(c) is-
𝜆𝑖 𝑒 −𝜆
(𝑃𝑎 )𝑡ℎ = ∑𝑐𝑖=0
𝑖!
Where, λ=np
n=sample size; p= Fraction defective of the lot.
PROCEDURE: For the given lot size N = 150
1. First set the acceptance number c = 0.
2. Mix predetermined number of green balls to the lot to get the % defective = 2 % or fraction
defective of the lot = 0.2 i.e., add three balls to the lot and remove 3 balls other than green
co lour from the lot so that the lot size remains = 150.
3. Take a sample of 20 balls from the lot of 150 balls.
4. Count the no. of defective items (green balls) in the sample.
5. Recovered whether the lot is acceptable or not i.e., if defective balls are less than or equal
to ‘C’, then note that the lot is acceptable.
6. Replace the sample of the balls into the lot.
7. Repeat the steps 3 to 6 ten times and compute the probability of acceptance of the lot Pa
(i.e., if 6 times the lot is accepted in repetitions then (Pa)a = 6/10 = 0.6.
8. Change the % defective to 4,6,8 and 10% by changing the green balls in the lot
correspondingly (i.e., add three balls each time and remove three balls other than green balls
from the lot so that the lot size remains the same (or = 150).
9. Repeat the steps 3 to 7 for each value of % defective.
10. Repeat the above procedure for other values of acceptance number c = 1 &2.
11. Also find the probability of acceptance of the lot theoretically for different values of %
defective corresponding to the values of C = 0,1 &2.
12. Plot the actual and theoretical probability of acceptance values for each value of C
(=0,1&2).
Sample Graphs
Acceptan Lot Defe Fraction % Samp Theoretic Defectives found in the sample No. of Actual
ce Size ctive of defectiv le size al 1 2 3 4 5 6 7 8 9 10 times probabilit
number ‘N’ s defectiv es in the (n) acceptan lot y= t/10
‘C’ place es in the lot ce (𝑃𝑎 )𝑡ℎ accept
d in lot ed (t)
the P=d/N
lot
‘d’
C=0 150 0 0.0 0 20 0.0
150 3 0.02 2 20 0.4
150 6 0.04 4 20 0.8
150 9 0.06 6 20 1.2
150 12 0.08 8 20 1.6
150 15 0.1 10 20 2
C=1 150 0 0.0 0 20 0.0
150 3 0.02 2 20 0.4
150 6 0.04 4 20 0.8
150 9 0.06 6 20 1.2
150 12 0.08 8 20 1.6
150 15 0.1 10 20 2
C=2 150 0 0.0 0 20 0.0
150 3 0.02 2 20 0.4
150 6 0.04 4 20 0.8
150 9 0.06 6 20 1.2
150 12 0.08 8 20 1.6
150 15 0.1 10 20 2
Experiment 4
Aim: To draw P-Chart for fraction defective and to check the control of the process for a
given set of board pins.
Apparatus Required:
1) Sample of board pins – 600 nos.
2) Tray – 1 no
Theory: The quality characteristics, which are not amendable to measurement, are called
attributes. Such characteristics can be identified by their presence or absence from the
product. For example, we may say that the surface of the plastic product is cracked or not
cracked. Whether castings produced are having surface defects or not, whether the bottles
that have been manufactured contain holes or not. Thus, attributes may be judged either by the
proportion or units that are defective or by the number of defects/units.
In general, the failure to meet the requirement imposed on an item with respect to a
single characteristic is called as a defect. An item the quality of which does not meet the
specified requirements is known as a defective item.
The most widely used attributes control chart is the P- chart. The attributes control
charts for fraction defective (or percent defective) is called the P-chart. Fraction defective
may be defined as the number of defective articles found in any inspection or series of
inspection to the number of articles actually inspected whereas percent defective is 100 times
the fraction defective. If ‘P’ represents fraction defective, then the expression for ‘P’ may be
written as
𝑁𝑜. 𝑜𝑓 𝑑𝑒𝑓𝑒𝑐𝑡𝑖𝑣𝑒𝑠 𝑖𝑛 𝑎 𝑠𝑢𝑏𝑔𝑟𝑜𝑢𝑝
𝑃=
𝑁𝑜. 𝑜𝑓 𝑖𝑛𝑠𝑝𝑒𝑐𝑡𝑒𝑑 𝑖𝑛 𝑡ℎ𝑒 𝑠𝑢𝑏𝑔𝑟𝑜𝑢𝑝
Percent defective = 100 P
Generally, in a production process a sample of items consisting of different subgroups
is taken and defective items for each subgroup are traced by using suitable inspection
methods. Then the fraction defective or percent defective per each subgroup will be
calculated and these values are plotted on P –chart.
The central line of the P – chart is expressed as
𝑃̅= average of all fraction defectives
𝑇𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑑𝑒𝑓𝑒𝑐𝑡𝑖𝑣𝑒𝑠
𝑃̅ =
𝑇𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑝𝑖𝑒𝑐𝑒𝑠 𝑖𝑛𝑠𝑝𝑒𝑐𝑡𝑒𝑑
The fraction defectives tend to approach binomial distribution and the control limits
−
(UCL & LCL) are set at 3 of the fractional defectives from mean 𝑃̅. Thus, the Upper and
lower control limits are given by
− −
𝑈𝐶𝐿𝑝 = 𝑃̅ + 3𝜎 𝑃 𝐿𝐶𝐿𝑝 = 𝑃̅ − 3𝜎 𝑃
Where, 𝜎 = Standard deviation of the distribution of the fraction defectives.
Whenever calculations give a negative value of LCL of P –chart, that limit is
recorded as zero.
PROCEDURE:
1) Take the random samples of size 50 each (n) and make 12 groups.
2) Observe the number of defective pins in each sample (𝑑𝑖 ).
3) Find the fraction defective in each sample (𝑑𝑖 / 𝑛). _
4) Calculate the center line or mean fraction defective ( 𝑃 = ∑ 𝑃𝑖 /12 ).
5) Compute the control limits (UCL & LCL)
𝑃̅(1 − 𝑃̅ )
𝑈𝐶𝐿𝑝 = 𝑃̅ + 3𝜎𝑃 = 𝑃̅ + 3√
𝑛
𝑃̅(1 − 𝑃̅)
𝐿𝐶𝐿𝑝 = 𝑃̅ − 3𝜎𝑃 = 𝑃̅ − 3√
𝑛
6) Draw the P- chart by plotting fraction defectives against each sample.
7) Comment the nature of control of the process.
OBSERVATIONS: sample size = n=50
Sample Number (i) Number of defective pins (𝑑𝑖 ) Fraction defectives of sample
𝑑
(𝑝𝑖 = 𝑛𝑖 )
1.
2.
3.
12.
CONCLUSION: If all the observations are with in the upper and lower limits of
P- chart, the process is under statistical quality control.
If any value lies outside the control limit, recalculate 𝑃̅, 𝑈𝐶𝐿𝑝, 𝐿𝐶𝐿𝑝 excluding the data for all those
outside lying points. Repeat the process until all values lie with in 𝑈𝐶𝐿𝑝 & 𝐿𝐶𝐿𝑝.
Sample graph
UCL
Fraction CL
defective of
sample
LCL=0
Sample
number LCL=-ve
Experiment 5
Aim: Determine the forecasted demand using two different approaches for a given data set and
compare the effectiveness of each approach.
Software used: MS excel
Theory: There are two main types of forecasting methods that financial analysts use to predict
future revenues, expenses, and capital costs for a business. While there are a wide range of
frequently used quantitative budget forecasting tools, in this article we focus on the top four
methods: (1) Straight line method (2) moving average method.
The straight-line method is one of the simplest and easy-to-follow forecasting methods. A financial
analyst uses historical figures and trends to predict future revenue growth. we will look at how
straight-line forecasting is done by a retail business that assumes a constant sales growth rate of
4% for the next five years.
Moving averages are a smoothing technique that looks at the underlying pattern of a set of data to
establish an estimate of future values. The most common types are the 3-month and 5-month
moving averages.
Procedure:
straight-line method
1. The first step in straight-line forecasting is to determine the sales growth rate that will be
used to calculate future revenues. For 2016, the growth rate was 4.0% based on historical
performance. We can use the formula =(C7-B7)/B7 to get this number. Assuming the
growth will remain constant into the future, we will use the same rate for 2017 – 2021.
2. To forecast future revenues, take the previous year’s figure and multiply it by the growth
rate. The formula used to calculate 2017 revenue is =C7*(1+D5).
3. Select cell D7 to H7, then use the shortcut Ctrl + R to copy the formula all the way to the
right.
Moving average Method
1. To perform a moving average forecast, the revenue data should be placed in the vertical
column. Create two columns, 3-month moving averages and 5-month moving averages.
2. The 3-month moving average is calculated by taking the average of the current and past
two months revenues. The first forecast should begin in March, which is cell C6. The
formula used is =AVERAGE(B4:B6), which calculates the average revenue from January
to March. Use Ctrl + D to copy the formula down through December.
3. Similarly, the 5-month moving average forecasts revenue starting the fifth period, which is
May. In cell D8, we use the formula =AVERAGE(B4:B8) to calculate the average revenue
for January to May. Copy the formula down using shortcut Ctrl + D.
4. It is always a good idea to create a line chart to show the difference between actual and
MA forecasted values in revenue forecasting methods. Notice that the 3-month MA varies
to a greater degree, with a significant increase or decrease in historic revenues compared
to the 5-month MA. When deciding the time period for a moving average technique, an
analyst should consider whether the forecasts should be more reflective of reality or if they
should smooth out recent fluctuations.
Experiment 6
Aim: To plot the tracking signal for the given demand.
Software Used: MS Excel
Theory: Tracking signal is a measure used to evalue if the actual demand does not reflect the
assumptions in the forecast about the level and perhaps trend in the demand profile. In Statistical
Process Control, people study when a process is going out of control and needs intervention.
Similarly Tracking signal tries to flag if there is a persistent tendency for actuals to be higher or
lower systematically. If Forecast is consistently lower than the actual demand quantity, then there
is persistent under forecasting and Tracking Signal will be positive. Tracking Signal is calculated
as the ratio of Cumulative Error divided by the mean absolute deviation. The cumulative error can
be positive or negative, so the TS can be positive or negative as well. TS should pass a threshold
test to be significant. If Tracking Signal > 3.75 then there is persistent under forecasting. On the
other hand, if this is less than -3.75 then, there is persistent over-forecasting. So in essence, |TS| >
3.75 implies a forecast bias ==> TS < -3.75 or TS > 3.75 implies a bias. So what is magical about
3.75. This is an approximation using the relationship between a normally distributed forecast error
and the Mean Absolute deviation. In General, Forecast Error (using RMSE) * 0.8 = MAD. At 99%
promised service level, you will be using a 3 Sigma level. As a measure of MAD, this translates
into 3.75 MAD hence the 3.75 as the threshold for TS.
∑𝑡(𝐴𝑐𝑡𝑢𝑎𝑙 𝑑𝑒𝑚𝑎𝑛𝑑 − 𝐹𝑜𝑟𝑒𝑐𝑎𝑠𝑡𝑒𝑑 𝑑𝑒𝑚𝑎𝑛𝑑)𝑡
𝑇𝑟𝑎𝑐𝑘𝑖𝑛𝑔 𝑠𝑖𝑔𝑛𝑎𝑙 =
𝑀𝐴𝐷
Procedure:
1. For the given demand, generate a moving average forecast.
2. Calculate mean absolute deviation using formulas in excel sheet.
3. Calculate the value of tracking signal using the formula given earlier. (t=12)
4. Repeat the experiment using exponential smoothening method and determine the better
performing forecasting technique.
Experiment 7
Aim: Minimize make span time for the given flow shop problem using different heuristics.
Software Used: MATLAB
Theory: Flow-shop scheduling is an optimization problem in computer science and operations
research. It is a variant of optimal job scheduling. Flow-shop scheduling is a special case of job-
shop scheduling where there is strict order of all operations to be performed on all jobs. Flow-shop
scheduling may apply as well to production facilities as to computing designs.
There are n machines and m jobs. Each job contains exactly m operations. The i-th operation of
the job must be executed on the i-th machine. No machine can perform more than one operation
simultaneously. For each operation of each job, execution time is specified.
Operations within one job must be performed in the specified order. The first operation gets
executed on the first machine, then (as the first operation is finished) the second operation on the
second machine, and so on until the n-th operation. Jobs can be executed in any order, however.
Problem definition implies that this job order is exactly the same for each machine. The problem
is to determine the optimal such arrangement, i.e. the one with the shortest possible total job
execution make span.
Procedure:
Johnson’s rule
1. Store the processing times on two machines in tow sets.
2.
a. (Johnsons Rule) Find the job with minimum processing time and determine the
machine to which it belongs.
b. R (Random) – Pick any Job in Queue with equal probability. This rule is often used
as benchmark for other rules
3. If j = 1 (machine 1) this job becomes the first job else, if j = 2 (machine 2) this job becomes
the last job.
4. Remove assigned job from the list and repeat until all tasks are assigned (break ties at
random)
Result: sequence (2,4,5,3,1), make span time=21 (Johnsons Rule)
Experiment 8
Aim: To draw the total cost curve and find the optimal strategy for a given problem considering
quantity discount and marginal quantity.
Software used: MS excel
Theory:
BIKO is a bike retailer located in the outskirts of Paris. BIKO purchases bikes from PMX in
orders of 250 bikes which is the current economic order quantity. PMX is now offering the
following bulk discounts to its customers:
• 2% discount on orders above 200 units
• 4% discount on orders above 500 units
• 6% discount on orders above 600 units
BIKO is wondering if the EOQ model is still the most economical and whether increasing the
order size would actually be more beneficial. Following information is relevant to forming the
decision:
• Annual demand is 5000 units
• Ordering cost is $100 per order
• Annual holding cost is comprised of the following:
• Warehousing cost of $6 per unit
• Purchase price is $200 per unit before discount
EOQ = √(2 x 100 (Order Cost) x 5000 (Annual Demand)) / (0.05x( 200×0.98) + 6 (Holding
Cost))
Procedure:
1. Find EOQ for all discount schemes using formula given above.
2. Include the scenarios with demand set at the end points (200, 400, 600).
3. Calculate ordering cost, holding cost for each scenario.
4. Find and store the total cost for each scenario in a series of columns
5. Using min function determine the best strategy.
Results: The following order quantity results in minimum cost. Q=___
Experiment 9
Aim: Evaluate the takt time using palmer, CDS and compare the result with branch and bound
technique.
Software Used: MATLAB / Python
Theory:
The flow shop scheduling problem can be solved using Johnsons rule, palmer heuristic, CDS
heuristic or branch and bound method.
Procedure: (Palmers Heuristic)
Consider the following four jobs three machine problem.
1. Check Johnsons rule. Checking the Johnsons rule for this problem results in
failure.
2. Store the Processing Time matrix in a list/set of dimension 4*3.
3. Based on number of machines (3 in our example), create a matrix (list / set) of
weights.
4. Multiply the weight matrix with processing time matrix to obtain weighted sum of
each job.
5. Define and use a function to perform job sequencing in descending order of
weighted matrix. The output of this function is simply the indices of weighted sum
matrix arranged in descending order of values.
6. Define and use a function to calculate completion time as follows.
7. Define and use a function to compute lower bound as follows.
8. Evaluate the goodness of the solution.
CDS Heuristic:
1. Define a function to covert a ‘m’ machine problem into two machine problem for
sequencing jobs.
2. Create a function to sequence job and compute completion time similar to Johnsons
heuristic.
3. Calculate goodness of the solution
Branch and Bound:
This method assigns jobs in stages. The job selected for further exploration (branching) at each
stage is the job resulting in lowest lower bounds on completion time. At the end of each stage
node (job) with minimum lower bound is explored until the solution is complete (i.e., node with
minimum bound cannot be branched any furhter).
1. Since all jobs are available for assignment in first stage, calculate and store completion
time for each possible assignment.
Jobs 𝑀1 𝑀2 𝑀3
1 3 4 10
2 11 1 5
3 7 9 13
4 10 12 2
Jobs 𝜎 𝜎′ Completion time
Assigned partial sequence Remaining jobs 𝑞1 𝑞2 𝑞3
𝑃1 1 2,3,4 3 7 17
𝑃2 2 1,3,4 11 12 17
𝑃3 3 1,2,4 7 16 29
𝑃4 4 1,2,3 10 22 34
2. Define and use a function to calculate the lower bounds using the following equations for
every partial sequence:
𝑏1 = 𝑞1 + ∑ 𝑡1𝑗 + min𝑗𝜖𝜎′ ([𝑡2𝑗 + 𝑡3𝑗 ])
𝑗𝜖𝜎′
𝑏2 = 𝑞2 + ∑ 𝑡2𝑗 + min𝑗𝜖𝜎′ ([𝑡3𝑗 ])
𝑗𝜖𝜎′
𝑏3 = 𝑞3 + ∑ 𝑡3𝑗
𝑗𝜖𝜎′
𝐵 = max (𝑏1 , 𝑏2 , 𝑏3 )
Jobs 𝑏1 𝑏2 𝑏3 𝐵
𝑃1 3+(11+7+10) + min (6,22,14) 7+(1+9+12) + min (5,13,2) 17+(5+13+2) 37
=37 =31 =37
𝑃2 11+(3+7+10) + min (14,22,14) 12+(4+9+12) + min (10,13,2) 17+(10+13+2) 45
=45 =39 =42
𝑃3 7+(3+11+10) + min (14,6,14) 16+(4+1+12) + min (10,5,2) 29+(10+5+2) 46
=37 =35 =46
𝑃4 10+(3+11+7) + min (14,6,22) 22+(4+1+9) + min (10,5,13) 24+(10+5+13) 52
=37 =41 52
3. Check if a complete solution is obtained and if it has the lowest bound. If not, begin next
stage by branching the job (node) with lowest lower bound.
P0
P1 P2 P3 P4
37 45 46 52 Lower
Bounds
P14
P12
P13
4. Calculate in and out time (completion time) of the newly branched partial sequences.
Similar to step 1, generate list of possible job assignment post the assignment of task with
lowest lower bound (i.e., job 1)
𝑀1 𝑀2 𝑀3
In Out In Out In Out
1 0 3 3 7 7 17
2 3 14 14 15 17 22
1 0 3 3 7 7 17
3 3 10 10 19 19 32
1 0 3 3 7 7 17
4 3 13 13 25 25 27
Jobs 𝜎 𝜎′ Completion time
Assigned partial sequence Remaining jobs 𝑞1 𝑞2 𝑞3
𝑃12 1,2 3,4 14 15 22
𝑃13 1,3 2,4 10 19 32
𝑃14 1,4 2,3 13 25 27
5. Calculate lower bounds of resulting sequences as in step 2
Jobs 𝑏1 𝑏2 𝑏3 𝐵
𝑃12 45 38 37 45
𝑃13 37 34 39 39
𝑃14 37 40 45 45
6. Since the node with lowest lower bound is still not completely explored, i.e., explore the
node 𝑃13 . By repeating step 3 and 4
P0
P1 P2 P3 P4
37 45 46 52
P12 P13 P14
45 39 45
P132 P134
𝑀1 𝑀2 𝑀3
In Out In Out In Out
1 0 3 3 7 7 17
3 3 10 10 19 19 32
2 10 21 21 22 32 37
1 0 3 3 7 7 17
3 3 10 10 19 19 32
4 10 20 20 32 32 34
Jobs 𝜎 𝜎′ Completion time
Assigned partial sequence Remaining jobs 𝑞1 𝑞2 𝑞3
𝑃132 1,3,2 4 21 22 37
𝑃134 1,3,4 2 20 32 34
Jobs 𝑏1 𝑏2 𝑏3 𝐵
𝑃132 21+(10) +(12+2) 22+12+2 37+2 45
=45 =36 =39
𝑃134 20+(11) +(1+5) 32+1+5 34+5 39
=37 =38 =39
P0
P1 P2 P3 P4
37 45 46 52
P12 P13 P14
45 39 45
P132 P134
45 39
Results:
The goodness of solution using the three methods for the two problems are:
Goodness of solution
Palmer method CDS Branch and Bound
Problem 1.
Problem 2.
Experiment 10
Aim: Find out the line efficiency for a given assembly line.
Software Used: MATLAB
Theory: An assembly line is a manufacturing process (often called a progressive assembly) in which
parts (usually interchangeable parts) are added as the semi-finished assembly moves from
workstation to workstation where the parts are added in sequence until the final assembly is
produced. By mechanically moving the parts to the assembly work and moving the semi-
finished assembly from work station to work station, a finished product can be assembled faster
and with less labor than by having workers carry parts to a stationary piece for assembly.
Consider the following problem
The production rate required is one assembly every 15 minute. Determine the minimum no of
workstations required so as to minimize the balance-delay
Procedure:
9. Store tasks time in a list with indexes corresponding to tasks.
10. Store the follower task indices for each task in separate list and name them the same
as task.
11. Calculate number of workstations as follows
𝑠𝑢𝑚 𝑜𝑓 𝑡𝑎𝑠𝑘 𝑡𝑖𝑚𝑒𝑠
𝑤𝑠 = =70/15=4.67= 5 (rounded)
𝐶𝑦𝑐𝑙𝑒 𝑡𝑖𝑚𝑒
12. choose a primary rule to determine the how tasks are to be assigned to workstations.
(Rule used here is to prioritize tasks with highest number of following tasks)
13. Generate a list of assigned task (empty in beginning) and start adding tasks (indices)
to this list based on priority rule. (Ties are broken based on longest task time)
14. Once all the tasks are added to assigned tasks, beginning with the fist workstation,
assign each task to a set, one at a time until the sum of task time is equal to or less
than cycle time (if assignment of last task exceeds CT, do not assign the task to
current station). Create an empty (WS) set and assign the newly created set to this
null set
15. Repeat step 6 until all tasks in the assigned tasks set are placed in a set and then in
WS
16. Calculate workstation time for each set in WS.
17. Determine no. of workstations (equal to number of sets inside WS)
𝑠𝑢𝑚 𝑜𝑓 𝑡𝑎𝑠𝑘 𝑡𝑖𝑚𝑒𝑠
𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦 =
𝐴𝑐𝑡𝑢𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑤𝑜𝑟𝑘𝑠𝑡𝑎𝑡𝑖𝑜𝑛𝑠 ∗ 𝑐𝑦𝑐𝑙𝑒 𝑡𝑖𝑚𝑒
