scheduling9.1resourceactivitymachineprocessormM1MmjobtasknJ1,J2,,Ji,JnJoperationJmmjO1j,O2j,,Omjjmachineschedulingproblemresourceconstrainedschedulingproblem11singlemachineparallelmachineJjprocessingtimepj+∈RpjidenticalparallelmachineuniformparallelmachineMisiJjMipijpj/siunrelatedparallelmachineJjMisijpijpj/sijserial1machineOijpijR+,OijijshopshopflowshopmO1j,O2j,,OmjopenshopJjJjO1j,O2j,,OmjjobshopflowshopJjmjJjO1j,O2j,,OmjjOijijjobshopJjOijOi+1,jiji+1,jjobshopjobshopJjmjpjJjreleasetime,readytime,releasedaterjJjduetimedjJjweightwjpreemptivenonpreemptiveJjJkJj,JkprecedencerelationJjJkJjcompletiontimeCjJjdjlatenessLi=Cj-djTj=max{0,Cj-dj}unitpenalty≤=10jjjdCUmaxj=1nCjCmaxLmaxmaxj=1nLjLmaxmaxj=1nTjmaxj=1nUjnj=1CjCjnj=1LjCjnj=1djnj=1TjTjnj=1UjUjJjwjnj=1wjCjwjCjnj=1wjTjwjTjnj=1wjUjwjUj29.2jobshopjobshopjobshopJ1,J2,JnJjO1j,O2j,,OmjjM1,M2,,MmO1j,O2j,,OmjjOijijpijjobshopJR9.4.1.9.4.2.PERT/CPMPERT(ProgramEvaluationandReviewTechnique)CPM(CriticalPathMethod)9.39.3.1Gantt1919GanttGanttGantt'schart9.1.3155100(a)1505103C(5)2C(3)1C(2)3B(2)2B(3)1B(5)3A(2)2A(4)1A(3)3A(2)3B(2)3C(5)2B(3)2A(4)2C(3)1B(5)1A(3)1C(2)123ABC(b)9.1.33jobshopGanttABC3123pijOijij(pij)ab9.3.2activity-on-nodediagramPERTLevy-Thompson-Wiest[1]CPM9.2.NP-[2][1]F.K.Levy,G.L.Thompson,andJ.D.Wiest.Introductiontothecritical-pathmethod.InJ.F.MuthandG.L.Thompson,editors,Industrialscheduling,chapter20,Prentice-Hall,1963.[2]M.S.KrishnamoorthyandN.Deo.Complexityoftheminimum-dummyactivitiesprobleminaPERTnetwork.Networks,9:189-194,1979.4ADBCADCB9.2.aABCDb9.3.3N0AOijOi+1,jsjO1jjOmj,jtMkNkNkdisjunctivearcEkUmkkEE1==G=(N,A,E)9.31A(3)2A(4)3A(2)3C(5)2C(3)1C(2)2B(3)3B(2)1B(5)ts9.3.a33jobshoppijOijij(pij)u,vEku,vv,uEkNkk51A(3)2A(4)3A(2)3C(5)2C(3)1C(2)2B(3)3B(2)1B(5)ts9.3.b33jobshopvN{s,t}vOijpijjobshops,tuvP(u,v)L(u,v)P(s,t)L(s,t)1A(3)2A(4)3A(2)3C(5)2C(3)1C(2)2B(3)3B(2)1B(5)ts9.3.c33jobshop1A(3)2A(4)3A(2)3C(5)2C(3)1C(2)2B(3)3B(2)1B(5)ts9.3.d33jobshop69.49.4.19.1.[activeschedule]9.2.[nondelayschedule]9.1.30040%[3]activeschedulegenerationschemeSJ\Seligiblejob1S02a1jbjcjSS2tcompletejobC(t)t[3]R.Kolisch.Serialandparallelresource-constrainedprojectschedulingproblem.EuropeanJournalofOperationalResearch,90:320-333,19967activejobA(t)CAtJ\(CA)t(t)1CA002a(t)(t)tbt(t)1jcjtdjAeAj'fj'ACgj'9.4.A(1;1)B(2;2)C(3;1)sCDBAb603CDBA(a)D(3;1)t036(c)9.4.ABCD42ast2bD0BDc0(0)={A,D}ADt=089.4.2t(t)1jpriorityrule,dispacthingrulej(t)vSPTshortestprocessingtimerulepj(t)jvvWSPTweightshortestprocessingtimerulewjpjv=wj/pjvdjEDDearliestduedateruleJacksonvvpriorityrulemethodmulti-priorityrulemethod[4]backwardschedulingmethodforward-backwardschedulingmethodrandomsamplingmethodbiasedrandomsamplingmethodv()()()∑∈=εγjjvjvjregretbasedbiasedrandomsamplingmethod()()()jvjvjvjε∈−=min~9[4]H.FisherandG.L.Thompson.Probabilisticlearningcombinationoflocaljob-shopschedulingrules.InJ.F.MuthandG.L.Thompson,editors,industrialscheduling,chapter15,Prentice-Hall,1963.