Забыли?

?

# What is a Job Shop?

код для вставкиСкачать
```Engineering Management Tidbits!
The Job Shop Game
Solving the NP Complete Scheduling Problem
James R. Holt, Ph.D., PE
Professor
Engineering Management
jholt@wsu.edu
http://www.engrmgt.wsu.edu/
1
What is a Job Shop?
вЂў
вЂў
вЂў
вЂў
вЂў
Say you have a shop that makes machine parts. Many, many types
of machine parts. You could have 50-100 machines and produces
2000 different parts.
Each part takes a different route through the machine shop using
different machines in different order. Some are drilled first. Some
are milled first. Some are cut, polished, ground. Others are not.
Some are turned, taped, threaded. Some are not.
Big parts take longer than small parts. Simple parts take shorter
paths than complex parts.
The algorithm to solve such a complex scheduling problems is
called вЂњNP complete.вЂќ That is, the number of computations needed
to find the optimal schedule is estimated to be some number raised
to the n power where n is the number of tasked to schedule. You
could do the math or simulate the system to find an answer. But,
it is faster to do the work than to calculate the optimal schedule.
Operations Researchers love to talk about Job Shop schedules,
but never solve them. I know, IвЂ™m one. So, I invented a Job Shop
Game.
2
A Simple Job Shop
вЂў Consider a simple shop with four operations: A, B, C, D and four
вЂў
products P1, P2, P3, P4.
Each product flows through four processes but not the same ones or in
the same order
In
A
B
Out
P1
P2
P3
P4
C
D
P1 goes: A->B->C->D Out
P2 goes: B->C->B->D Out
P3 goes: A->C->D->B Out
P4 goes: A->B->B->C Out
3
The Job Shop Game
вЂў LetвЂ™s use this simple Job Shop
In
A
B
вЂў
P1
P2
P3
P4
Out
C
D
such processes.
Here are some world wide web
playing this game:
п‚§ Video Instruction
п‚§ Instructions
п‚§ Playing Cards
п‚§ Blank Recording Sheets
(may look funny but prints fine)
вЂў IвЂ™ll explain a bit about the game in
the next few slides.
4
The Playing Cards
вЂў Here is a typical order card. This
вЂў
вЂў
вЂў
вЂў
one is for Product 4.
On the left is the Routing path
(first to A, then to B, and then
operation, then to C and out).
At the top is the Release Day line.
On this line the Gate Keeper
records the date the order was
released to the shop floor.
Each operation has a box to write
the date their process was
completed.
Flow time is the last operation
completion date minus release
date.
5
The Four Product types
вЂў There are four on one page at
вЂў
вЂў
вЂў
Playing Cards
Print out 5+ copies of the Playing
Card page for each game. Cut out
the order cards. You should have
at least 20 cards (equal numbers of
P1, P2, P3, P4)
For the first game, shuffle the 20
cards.
We will be playing the game until
all the order cards are processed
(just short of 35 days for 20 cards).
6
The Play
вЂў You need these people: Assign
a Gate Keeper, a person for
each operation (A, B, C, D) and a
Recorder.(Hard to do alone, but you
could)
вЂў Each operation can perform a
вЂў
maximum of one operation per
day. The operation is
documented by writing the date
in the appropriate Routing Box
The Gate Keeper holds the
shuffled stack of Order Cards.
Each day, the Gate Keeper
writes the day on the Release
Day line and calls out loud the
day (so the operations will know
which number to write).
7
The Play
Product #2
Product #1
Start
B
Start
A
D
Finish
B
A
D
C
C
Product #3
B
Start
вЂў After the operator writes a date
A
Product #4
Finish
D
C
B
Start
A
C
in the Routing Box (or the Gate
Keeper releases the Order Card)
the order advances to the next
Finish
operation where it waits for the
next day (or longer) to be
completed.
вЂў The routing must be followed
one operation per day.
вЂў Each operator can only write a
D
number if they have an Order
Card that needs their operation
Finish
on that day.
вЂў Sounds complicated, but its not.
IвЂ™ll show you a couple of days.
8
The Play
3
1
2
3
2
3
Assume the first card in the shuffled deck is
Product 2. As the play starts, the Gate Keeper
calls out loud, вЂњDay 1вЂќ and writes a вЂњ1вЂќ. No one
else has work.
Assume the second card in the deck is Product
3. As the play starts, the Gate Keeper calls out
loud, вЂњDay 2вЂќ and writes a вЂњ2вЂќ on the Product 3
Card.
On Day 2, Operation B can work and writes a
вЂњ2вЂќ.
вЂњDay 3,вЂќ the Gate Keeper calls out and writes
on a Product 1 Order Card.
On Day 3, both Operation C and A have work.
The Gate Keeper releases one card per day
until the Order Cards are gone.
9
Calculating Flow Days
вЂў
вЂў
4
вЂў
5
вЂў
вЂў
9
10
On Day 5 (or maybe 6) the first job
will finish and come to the recorder.
The recorder subtracts the Release
Day from the Last Operation to
calculate the total flow days for the
Product.
Here, Product #4 was released on
Day 4, finished A on day 5, finished
first B on day 9, finished second B on
day 10, finished C on day 12.
The flow days then are 12-4=8days
The flow days number is recorded on
two charts
12
8
10
Record Keeper
On the left are two charts (turned to be
The top chart (left most) is a scatter plot
of the Day Released versus Flow days.
There is one Order released each Day.
Put an X for the flow days are for each
completed order.
x
x
The second chart (right most) is a
histogram of the number of times a
particular flow day occurred. IвЂ™ll but an
вЂ�xвЂ™ for the first 8 flow days. There will
probably be many orders with 8 flow
days
11
and Histogram (first Game)
28
26
No. of FLO W DAYS
x
Notice the trend line.
What would you forecast
would you make for the
order released on the
35th day?
24
22
x
x
x
20
x
18
16
x
x
x
22
23
x
x
x
27
28
x
14
x
12
x
x
10
x
x
x
8
x
6
x
x
x
3
4
x
x
x
x
x
10
11
x
4
2
1
2
5
6
7
8
9
12
13
14
15
16
17
18
19
20
21
24
25
26
29
30
31
32
33
34
35
36
O R D E R S (in R e le a s e D a y s e q u e n c e )
No. of ORDERS
12
11
10
Can you see how much
variability there is in
the number of flow
days expected?
9
8
7
6
x
5
x
x
4
3
x
x
2
x
x
x
x
x
5
6
7
1
1
2
3
4
x
x
x
8
x
x
x
x
x
9
10
11
12
x
x
13
x
x
x
x
x
14
15
16
17
x
18
19
x
20
21
x
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
F L O W D A Y S (D is trib u tio n )
12
Second Game.
Play again juggling the release order
using the best schedule you can find.
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
Play the Job Shop again
This time, donвЂ™t shuffle the deck of Order Cards.
Sit down and thoughtfully schedule the cards.
Get all the best ideas from your group (Max of 10 min
discussion).
Now, with a better sequence (better than random), how well did
your charts look? Much better? A bit Better? No Change?
What was the difference in the final completion date? Did you
finish sooner?
What would you predict would be the flow days for a job
released on Day 35?
13
Third Game
DBR in the Job Shop
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
Play the Job Shop Game one last time. This time use Drum-Buffer-Rope.
The Drum is the B process. The Buffer is: вЂњThe Number of Days of
Uncompleted Work released to the floor that is Awaiting BвЂќ wherever it is.
You can try 5 days, 6 days or 7 days of work (you decide).
The Rope is a choke on the Gate Keeper. Each day, the Gate Keeper
assess how many products in process have empty Routing Boxes for B.
Look at all WIP to find them. If the WIP of uncompleted B operations
exceeds the вЂ�Buffer SizeвЂ™, then NO NEW WORK IS RELEASED THAT DAY.
If the number of B operations yet to be done, is less than вЂ�Buffer sizeвЂ™,
then RELEASE WORK that day.
This is scary! You are not releasing work to the floor a third of the time!
Now, do your charts look any worse? Much better? A bit Better? No
Change?
What was the difference in the final completion date? Did you finish
sooner?
What would you predict would be the flow days for a job released on Day
35?
14
Washington State UniversityвЂ™s
Engineering Management Program
http://www.engrmgt.wsu.edu/
Typical Results from DBR
28
вЂў
D A YS
26
N o. of FLO W
вЂў Have fun with the Job Shop
24
22
20
18
16
14
вЂў
12
x
10
x
8
x
6
x
4
x x
x x x x
x
x
x
x
x
x x
x
x x
x
x
x
x
x x
x x
2
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Game. There is lots to learn!
There are versions for those who
need variability and more
complexity if you want them.
http://www.wsu.edu/~engrmgmt/holt/e
m530/
O R D E R S (in Rele ase Day seq uence )
Interactive Live Lectures
over the Internet in the
evenings Pacific Time
Zone.
Keep Thinking!
Dr Holt
See you there!
N o. of O R D E R S
12
11
10
9
x x
8
x x
7
x x
6
x x
5
x x
4
x x x
3
x x x
2
x x x x
1
x x x x x x x
1
2
3
4
5
6
7
x
8
9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
F L O W D A Y S (Distribu tion)