form rincian soal ujian mata kuliah co or.doc
Post on 03-Apr-2018
233 Views
Preview:
TRANSCRIPT
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
1/29
Session 18 Layout Design
Production Line Balancing.
.
D 0 8 5 4Supply Chain : Manufacturing and Warehousing
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
2/29
Bina Nusantara University
2
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
3/29
Bina Nusantara University
3
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
4/29
Assembly line balancing is traditionally thought of as afacilities design and layout problem
There are a variety of factors that contribute to the difficulty of the problem Precedence constrains: some tasks may have to be completed in a
particular sequence Zoning restriction: Some tasks cannot be performed at the same
workstation
Let t 1, t 2, , t n be the time required to complete the respectivetasks
Assembly Line Balancing
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
5/29
The total work content (time) associated with the production of anitem, say T , is given by
Assembly Line Balancing
==n
iit T 1
For a cycle time of C, the minimum number of workstations possibleis [ T /C], where the brackets indicate that the value of T /C is to berounded to the next larger integer
Ranked positional weight technique: the method places a weight oneach task based on the total time required by all of the succeedingtasks. Tasks are assigned sequentially to stations based on theseweights
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
6/29
Assembly Line Balancing
Example 8.11 The Final assembly of Noname personal computers, a generic mail-order PCclone, requires a total of 12 tasks. The assembly is done at the Lubbock,
Texas, plant using various components imported from the Far East. Thenetwork representation of this particular problem is given in the following
figure.
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
7/29
Precondition The job times and precedence relationships for thisproblem are summarized in the table below.
Task Immediate Predecessors Time1 _ 12
2 1 63 2 64 2 25 2 26 2 127 3, 4 78 7 5
9 5 110 9, 6 411 8, 10 6
12 11 7
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
8/29
Assembly Line Balancing:Assembly Line Balancing:Helgeson and Birnie Heuristic (1961)Helgeson and Birnie Heuristic (1961)
Ranked positional weight technique
The solution precedence requires determining the positional weight of each task.
The positional weight of task i is defined as the time required toperform task i plus the times required to perform alltasks having task i as a predecessor.
t3 + t 7 + t 8 + t 11 + t 12 = 31Task Time Positional
Weight
1 12 702 6 58
3 6 31
4 2 27
5 2 20
6 12 29
7 7 25
8 5 18
9 1 18
10 4 17
11 6 1312 7 7
The ranking: 1, 2, 3, 6, 4, 7, 5, 8, 9, 10, 11, 12
ti = 70, and the production rate is a unit per 15 minutes;The minimum number of workstations = [70 / 15] = 5
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
9/29
Assembly Line Balancing:Helgeson and Birnie Heuristic (1961)
The ranking: 1, 2, 3, 6, 4, 7, 5, 8, 9, 10, 11,
12
Task ImmediatePredecessors
Time
1 _ 12
2 1 63 2 64 2 25 2 2
6 2 127 3, 4 78 7 59 5 1
10 9, 6 411 8, 10 612 11 7
Station 1 2 3 4 5 6
Tasks 1 2, 3, 4 5, 6, 9 7, 8 10, 11 12
Processing time 12 14 15 12 10 7
Idle time 3 1 0 3 5 8
C=15
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
10/29
T2=6
C=15
Station 1 2 3 4 5 6
Tasks 1 2,3,4 5,6,9 7,8 10,11 12
Processing time 12 14 15 12 10 7
Idle time 3 1 0 3 5 8
Cycle Time=15
T1=12
T2=6 T3=6 T4=2
T5=2 T6=12 T9=1
T5=2
T8=5T7=7 T10=4
T10=4 T11=6 T12=7
T12=7
15 Evaluate the balancing results bythe efficiency ti/NC
The efficiencies for C=15 is 77.7%,C=16 is 87.5%, andC=13 is 89.7% isthe best one
Helgeson and Birnie Heuristic (1961)
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
11/29
C=15
Station 1 2 3 4 5 6
Tasks 1 2,3,4 5,6,9 7,8 10,11 12
Processing time 12 14 15 12 10 7
Idle time 3 1 0 3 5 8
Helgeson and Birnie Heuristic (1961)Helgeson and Birnie Heuristic (1961)
Station 1 2 3 4 5
Tasks 1 2,3,4,5
6,9 7,8,10 11,12
Idle time 4 0 3 0 3
C=16Increasing the cycletime from 15 to 16,the total idle timehas been cut downfrom 20 min/units to10 improvement in
balancing rate.
The production ratehas to be reduced fromone unit/15 minutes toone unit/16minute;
Station 1 2 3 4 5 6
Tasks 1 2,3 6 4,5,7,9 8,10 11,12
Idle time 1 1 1 1 4 0
C=13
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
12/29
C=15
Station 1 2 3 4 5 6
Tasks 1 2,3,4 5,6,9 7,8 10,11 12
Processing time 12 14 15 12 10 7
Idle time 3 1 0 3 5 8
Helgeson and Birnie Heuristic (1961)
Station 1 2 3 4 5
Tasks 1 2,3,4,5
6,9 7,8,10 11,12
Idle time 4 0 3 0 3
C=16
Station 1 2 3 4 5 6
Tasks 1 2,3 6 4,5,7,9 8,10 11,12
Idle time 1 1 1 1 4 0
C=13
13 minutes appear to be the minimumcycle time with sixstation balance.
Increasing thenumber of stationsfrom 5 to 6 resultsin a greatimprovement in
production rate;
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
13/29
Stochastic Scheduling: Static Case
Single machine case: Suppose that processing times are randomvariables. If the objective is to minimize average weighted flow time,
jobs are sequenced according to expected weighted SPT. That is, if jobtimes are t 1, t 2, . . ., and the respective weights are u 1, u 2, . . . then job i precedes job i+1 if
E(t i )/u i < E(t i+1 )/u i+1
Multiple Machines: Requires the assumption that the distribution of jobtimes is exponential, (memoryless property). Assume parallelprocessing of n jobs on two machines. Then the optimal sequence is toto schedule the jobs according to LEPT (longest expected processingtime first).
Johnsons algorithm for scheduling n jobs on two machines in thedeterministic case has a natural extension to the stochastic case aslong as the job times are exponentially distributed.
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
14/29
Stochastic Scheduling: Queueing Theory
A typical queueing process
The basic phenomenon of queueing arises whenever a shared facility needs tobe accessed for service by a large number of jobs or customers. (Bose)
The study of the waiting times, lengths, and other properties of queues.(Mathworld)
Applications:
Telecommunications Health servicesTraffic control Predicting computer performance
Airport traffic, airline ticket sales Layout of manufacturing systemsDetermining the sequence of computer operations
Service FacilityCustomers arriving Served customers leaving
Discouraged customers leaving
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
15/29
Examples of Queueing Theory
http://www.bsbpa.umkc.edu/classes/ashley/Chaptr14/sld006.htm
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
16/29
Stochastic Scheduling: Dynamic Analysis
View network as collections of queues
FIFO data-structures
Queuing theory provides probabilistic analysis of these queues
Typical operating characteristics of interest include: Lq = Average number of units in line waiting for service
L = Average number of units in the system (in line waiting for service andbeing serviced)
Wq = Average time a unit spends in line waiting for service W = Average time a unit spends in the system Pw = Probability that an arriving unit has to wait for service Pn = Probability of having exactly n units in the system P0 = Probability of having no units in the system (idle time) U = Utilization factor, % of time that all servers are busy
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
17/29
Characteristics of Queueing Processes
Arrival pattern of customers
Service pattern of servers
Queue discipline
System capacity
Number of service channels
Number of service stages
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
18/29
Characteristics of Queueing Processes
Arrival pattern of customers Probability distribution describing the times between successive
customer arrivals Time independent Stationary arrival patterns Time dependent Non-stationary
Batch or Bulk customer arrivals Probability distribution describing the size of the batch
Customers behavior while waiting Wait no matter how long the queue becomes
If the queue is too long, customer may choose not to enterinto the system
Enter, wait, and choose to leave without being serviced If there is more than one waiting line, customer may
switch jockey
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
19/29
Characteristics of Queueing Processes
Arrival pattern of customers
Service pattern of servers Single or Batch May depend on the number of customers waiting state dependent Stationary or Non-stationary
Queue discipline Manner in with customers are selected to service First Come First Served (FCFS) Last Come First Served (LCLS) Random Selection for Service (RSS) Priority Schemes
Preemptive case Non-preemptive case
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
20/29
Characteristics of Queueing Processes
Arrival pattern of customers Service pattern of servers Queue discipline System capacity
Finite queueing situations = Limiting amount of waiting room
Number of service channels Single-channel system Multi-channel system, generally assumed that parallel channels
operate independently of each other
Number of service stages
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
21/29
Notation Used in Queueing Processes
Full notation: A / B / X / Y / Z Shorthand: A / B / X
A indicates the interarrival-time distribution Assumes: Y is infinity,B the probability distribution for service time Z = FCFSX number of parallel service channels
Y the restriction on system capacityZ the queue discipline (FCFS)
Symbol = Explanation
AB
M = Exponential, D = Deterministic, E k = Erlang type
Hk = Mixture of k exponentials, PH = Phase type, G = General
X Y
1, 2, ... , infinity1, 2, ... , infinity
Z FCFS, LCLS, RSS, PR = priority, GD = general discipline
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
22/29
Queueing Processes: Littles Formulas
One of the most powerful relationships in queueing theory was developed by
John D.C. Little in the early 1960s.Formulas:
and ,
where is an average rate of customers entering the system, and
W is an expected time customer will spend in the system
W L = qq W L =
1
2
3
Number of customersin system
Time, t
t1 t2 t3 t4 t5 t6 t7 T
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
23/29
Poisson Process & Exponential Distribution
M: stands for "Markovian", implying exponential distribution for servicetimes or inter-arrival times, that carries the memoryless property
past state of the system does not help to predict next arrival / departure
n+1nn-1
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
24/29
Calculating ExpectedSystem Measures for M/M/1
The utilization rate: = / P0= 1
P i= i(1 ), for i = 1, 2, 3,
these formulas hold only if < 210
CHARACTERISTIC SYMBOL FORMULA
Utilization / Exp. No. in System L / ( ) = / (1-)Exp. No. in Queue Lq 2/ ( ) = 2 / (1-)Exp. Waiting Time W=L/ 1 / ( ) = / (1-)Exp. Time in Queue W q=L q / / ( ) = 2 / (1-)Prob. System is Empty P 0 1 ( / ) = 1 -
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
25/29
Calculating ExpectedSystem Measures for M/M/m
http://www.ece.msstate.edu/~hu/courses/spring03/notes/note4.ppt
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
26/29
Calculating ExpectedSystem Measures for M/M/m
Assumption- m servers- all servers have the same service rate - single queue for access to the servers- arrival rate n =
- departure rate
( )( )+=
==
,1,,
1,,2,1,0,
mmnm
mnnn
m-1 m m+1210
m
mm(m-1)32
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
27/29
Calculating ExpectedSystem Measures for M/M/m
( ) ( )( )1
11
00 1!!
=+=
mm
nm
P mm
n
n
( ) 021
1! P
m
m L
mm
q
=
+
m L L q += qq LW = 1+= qW W
m-1 m m+1210
m
mm(m-1)32
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
28/29
Example
Unisex hair salon runs on a first-come, first-served basis. Customersseem to arrive according to a Poisson process with mean arrival rateof 5/hr. Because of Ms. H.R. Cutts excellent reputation, customersare always willing to wait. Average service time of 10 min isexponentially distributed.
Calculate the average number of customers in the shop and theaverage number of customers waiting for a haircut.
Calculate the percentage of time an arrival can walk right in withouthaving to wait at all.
The waiting room has only 4 seats. What is the probability that acustomer upon arrival rill have to stand?
Calculate average system waiting time, and the line delay.
-
7/28/2019 Form rincian soal ujian mata kuliah CO OR.doc
29/29
Other Systems
M/M/1/K - system with a capacity K eff = effective arrival rate
M/D/1; M/G/1; M/G/
Assignment: download the QTS add-in for Excel software to check the homework problems answers
http://www.geocities.com/qtsplus/DownloadInstructions.htm#DOhttp://www.geocities.com/qtsplus/DownloadInstructions.htm#DOWNLOAD_INSTRUCTIONSWNLOAD_INSTRUCTIONS
top related