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/ В© Washington State University-2010 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. В© Washington State University-2010 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 В© Washington State University-2010 3 The Job Shop Game вЂў LetвЂ™s use this simple Job Shop In A B вЂў P1 P2 P3 P4 Out C D and develop our intuition about such processes. Here are some world wide web links to detailed instructions about 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. В© Washington State University-2010 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 return to B for a second 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. В© Washington State University-2010 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). В© Washington State University-2010 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). В© Washington State University-2010 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 and each Order only receives 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. В© Washington State University-2010 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. В© Washington State University-2010 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 В© Washington State University-2010 10 Record Keeper On the left are two charts (turned to be on this page--so tilt your head). 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 В© Washington State University-2010 11 Traditional Results for Scatter Plot 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 ) В© Washington State University-2010 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). Sequence the Order cards to take advantage of your constraint. 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? How confident would you be about your prediction? В© Washington State University-2010 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? How confident would you be about your prediction? В© Washington State University-2010 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. More information is available at: 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) В© Washington State University-2010 15

1/--страниц