ࡱ> vxu7 [bjbjUU jH7|7| rl****z'z'z'z','t{2&(&(&(&(&(WWW,{.{.{.{.{.{.{$| ~XR{WM WWWR{eY**&(&(%g{eYeYeYW(*&(&(,{eYW,{eYeY[Hvt ,{&(( ԗz'Wy^,{}{0{zWXpW,{eY****Lecture 1 Introduction Scheduling is the allocation of scarce resources to tasks over time. Topics in this class Modeling and formulating scheduling problems Algorithms for solving scheduling problems Understanding hard vs. easy problems Analysis Tools Algorithm design and analysis of running times Solution quality NP-completeness Probability Linear programming Dynamic programming Four components of a scheduling problems Tasks Resources Constraints Objective Examples Project Scheduling: System Installation Development and installation of trading tools for the Frankfurt Stock Exchange by Deutsche Brse group Tasks: 300 software projects. Resources: 200 types of employees, 1500 people Constraints: Projects may be interrelated by - precedence constraints - milestones - joint use of resources Objective: minimize makespan 2) Hot Strip Mill Production Scheduling Integrated steel plant, Acme Steel, Chicago The mill transforms large bars of steel (slabs) into coils of sheet Tasks: Select orders and sequence them Resources: machines Objectives: - Minimize set-up times, smooth production - Minimize waste of energy - Minimize number of delayed orders Constraints: - Product quality restrictions - Process efficiency standards 3) Flight Crew Scheduling American Airlines: crew costs are the 2nd highest component of direct operating cost Tasks: Allocate flights into crew trips Resources: Crew Objective: minimize the total cost of flying the schedule - Cost components: salaries, hotel expenses, etc. Constraints: - limitations of work rules (shaped by a union contract) - limits on flight time, connection time 4) Robot Scheduling in a Circuit Board Production Line Control of robots requires real-time scheduling A circuit board must be sequentially processed within a series of chemical tanks A board can stay in a tank for a fixed time, otherwise it becomes defective Tasks: Circuit board Resrouces: Chemical tanks Robots move the board from station to station Scheduler decides which job to pick next Objective: maximize throughput of good parts Constraints: fixed sequence for jobs      5) Sequencing of Commercial Breaks by TV Networks Management of commercial airtime at Channel 4 5 min break may contain 180 spots across 6 regions Tasks: Commercials Resrouces: Time spots in a region Constraints: -No overlaps or gaps -advertisers may specify first or last spot Objective: maximize no of advertiser requests 6) Assigning CPU time to tasks Tasks: computer jobs with processing time and priority Resources: computers Constraints: use of memory and disk Objective: response time or fairness 7) Automobile factory. Tasks: car Resources: assembly machines and labor Constraints: -ordering on the various operations that go into creating a car, e.g. body, axles, tires, glass, engine, electrical, exhaust, etc. each machine can only work on one car at once each worker can only work on one car at once. Objective: throughput -- # of cars produced per time period Scheduling in Manufacturing                      Scheduling in Services          Shop floor Job loading Data collection Shop floor management Shop status Dispatching Schedule Scheduling performance Detailed scheduling Scheduling and rescheduling Shop orders, Release dates Scheduling constraints Material requirements planning, capacity planning Material requirements Quantities, due dates Capacity status Production planning, master scheduling Orders, demand forecasts Customer Orders, reservations Accept/ reject Pricing Yield management Scheduling Data Forecasts Database Database Status Material Handling Hoist 5 4 3 2 1 Chemical Tanks )f{|?AQTceps'(5>*CJ \aJ mHnHu5CJ \aJ mHnHu"5B*CJ$\aJ$mHnHphu5CJ(\aJ(mHnHu5CJ$\aJ$mHnHu mHnHuCJ$ 6CJ$] 56>*B*CJ$\]aJ$ph56B*CJ$\]aJ$ph 5CJ(\>*2def{|@ARSTdeqr & F)h^h & F($a$$a$Zrs'( & F & F,$a$ & F, & F)h^h '4MNkl 0DEQR}^ & F & F$a$ & F` & F & F  'NXbkm 0:EQ & | # 0 $ . R ^ z |  򼰨jUmHnHu5>*CJ \aJ 5CJ \aJ 5B*CJ$\aJ$ph5CJ$\aJ$"5B*CJ$\aJ$mHnHphu5CJ$\aJ$mHnHu5>*CJ \aJ mHnHu5CJ \aJ mHnHu: % & { | " # 0 i $a$ & F  & F & F & F h^` & F^ N O # $ Q R w x y z   & F% & F$ & F# & F" & F!  = > R S u v  & F'^ & F& & F! > E Q ^ t u v PZeq *,.@\^_bcdegiklnorsuwxz|~ǺǺǺǺǺǺǺǺǺǺǺǺǺǺǺǺǺ5CJ$\aJ$mHnHujUmHnHu5CJ$\aJ$CJ$CJ$aJ 5>*CJ \aJ 5CJ \aJ 5B*CJ$\aJ$phIPe+,-./0123456$a$ & F,p^p & F'6789:;<=>?@\_cehilosvwyz}~$a$$a$"#9:FGST]^uv12IJY[ 5CJ\aJ5>*B*CJ$\aJ$ph5CJ$\aJ$mHnHujUmHnHuS$a$"#9:?FGST]^iuv$a$$12?IJSZ[p$a$ !39:<=?@$a$  !9:<=?@BCEFHIX[5\5CJ\aJ@BCEFHIXYZ[$a$ hP+p,p-p.p/R / =!0"0#*$`%4567 i8@8 NormalCJ_HaJmH sH tH 6`6 Heading 1$@& 5CJ(\<A@< Default Paragraph FontJC`J Body Text Indent h^h5CJ \aJ  *;R_lv3Jbs '19RUX[^aq[      }~ *;R_lv3Jbs '19RUX[^aqt      !"#$%&'()*+,-./01234[Hdef{|@ARSTdeqrs'( '4MNkl 0DEQR}  %&{|"#0iNO#$QRwxyz = > R S u v   P e  + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ \ _ c e h i l o s v w y z } ~      " # 9 : ? F G S T ] ^ i u v  $12?IJSZ[p !39:<=?@BCEFHIXY\000000000f( 0f0f( 0f0f( 0f0f00) 00) 000) 00) 000) 00) 000, 0, 0, 0, 000000000000, 00 00 00 00 000000 0000 00 0 0 00 000000 0000000 00 0 00 0000 0000000! 00! 00" 0" 0" 00# 00$ 00% 00% 00000000000000000! 00! 00! 00! 00& 00000' 0000000' 0' 0' 0' 000000' 0' 0' 00, 0, 0' 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000  ["r 6@[ !#Z8@d%\%(  z  00?" 0z  01?" 1z  02?" 2z  03?" 3z  04?" 4\B b S DjJ"\B c S DjJ"\B d S DjJ"\B e S DjJ"\B f S DjJ"\B g S DjJ"\B h S DjJ" \B i S DjJ" \B j S DjJ" \B k S DjJ" \B l S DjJ" \B m S DjJ"\B n S DjJ"\B o S DjJ"\B p S DjJ"\B q S DjJ"\B r S DjJ"D2 s  jJ"D2 t  jJ"D2 u  jJ"|h P  v 3"z w 0jJ?"$<z" x 0jJ?"Bz y 0jJ?"J;z z 0jJ?"~z { 0jJ?"~ z | 0jJ?" ~P z } 0/?" /z ~ 05?" 5\  3 "" "\B  S D"#\  3  ""  \  3 #" #b  C "% b  C "/ b  C "6 b  C "< b  C "B b  C !"! !\  3 "$ \B  S D",VB @ C D"'VB  C D" \B  S D"*\B  S D"VB  C D")VB @ C D".VB @ C D"=VB @ C D"9VB  C D"8\B  S D"2VB  C D"1\B  S D"7\B  S D"5\B  S D":\B  S D"?\B  S D">\  3 "A \  3 "@ \  3 "; \  3 "4 \  3 "+ \  3 "( \  3 "0 \  3 "3 V  C jJ"-\B @ S D"\B  S D"&\  3 -"D -\  3 ,"E ,b  C )"K )\  3 ("L (\  3 $"T $\  3 ."C .\  3 +"I +\  3 '"M '\  3 *"J *\  3 %"S %\  3 &"Q &\B  S D"R\B  S D"H\B @ S D"N\B  S D"F\B  S D"P\B  S D"G\B  S D"OB S  ?z{\ ] _ ` a c e f i j l m o p q s t w z { ~  [vd` tb@VVt}^>tc@tuNtt  Nts0Ntn@~@tm~tl~tk@~@tj~ti~th` ~` tg ~ tf~td`~`t`ttxTt tBtr@tq@tpto ` te`t~ NtVP"Ft V`t`  tP tPPt  tP`ttP0!t 4tPtP tp0tPPtP tP0ntlt2tP t "t[!tPPytP tpmPtPt[Kt OtP! !tP!P tP tt7Pt 9tP t` ` t  t@ at@at %et0`<t` Nt0!Nt  tt  bt"t0D t`z t0!Jt0`t t ~ >t~>t 0t t t` tS \ \.9    ! ? E i t  $0?BSYpv\33333333333333333333&&lm , \ cliff steinHC:\Documents and Settings\cliff\My Documents\ieor4405\lec 1 examples.doc cliff steingC:\Documents and Settings\cliff\Application Data\Microsoft\Word\AutoRecovery save of lec 1 examples.asd cliff steingC:\Documents and Settings\cliff\Application Data\Microsoft\Word\AutoRecovery save of lec 1 examples.asd,v  z7  B  6$ E=  y F\ #8^H^  ~" IX&&Q;( 6y) f. u. Hg/ ]e0 ~2 d3 ,< thF dyI j)NM!9PFWOT..`KU M"U ,\W SY Y[ H,` %d hd,35,f ~ h Uvj zj $n ds >wt {t /~u .Wv ({ hh^h`OJQJ^Jo( ^`OJQJo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(h ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(hh^h`.hh^h`OJQJ^Jo(h^`.z^`zo()$ $ ^$ `OJPJQJ^Jo(-h@ @ ^@ `.h^`.hL^`L.h^`.h^`.hPLP^P`L.hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hhh^h`.h88^8`.hL^`L.h  ^ `.h  ^ `.hxLx^x`L.hHH^H`.h^`.hL^`L.h ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`.hh^h`OJQJ^Jo(hhh^h`.h88^8`.hL^`L.h  ^ `.h  ^ `.hxLx^x`L.hHH^H`.h^`.hL^`L.hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`o(.hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(hh^h`OJQJ^Jo(,~ hj)N,<~"5,fQ;(thFv ds]e0~2>wtY[6y)Uvj%d{tF\dyI^ 6$$nu.`KUH,`yE= f.Hg/.WvSY/~u,\WB d3zj({M"Uz7 #8^WOThd!9PIX&,,          Ndfjz                                 @ ĕ [P@UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier New;Wingdings"qh[q&ߚ&' !0*20 l 2Q cliff stein cliff steinOh+'0l   ( 4 @LT\d ss cliff steinliflifNormalt cliff stein4ifMicrosoft Word 9.0@r@r@zM ՜.+,0 hp  columbia university   Title  !"#$&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdfghijklnopqrstwRoot Entry F߷y1Table%WWordDocumentjHSummaryInformation(eDocumentSummaryInformation8mCompObjjObjectPool߷߷  FMicrosoft Word Document MSWordDocWord.Document.89q