资源描述
Outline,DeepintoSGalgorithm。SolveparallelmachineschedulingusingL-GmethodSimulationanalysis,DeepintoSGmethod,Widelyusedinnon-differentiableoptimization;Minf(x),dual,1.寻找到下界2.得到一个初始的解,illustrationfordualproblems,原问题：寻找使得目标值最小的x,对偶问题：寻找使得目标函数最大的,StepsofSG,Step1:选一个初始拉格朗日乘子如0,t=1;Step2：对于从中任选一个次梯度；若0则达到了最优解而停止计算；否则，t=t+1,重复STEP2；,IllustrationofSG,upper1,上升很慢,Gama,Lemma1：whenLemma2：andforallk,thenHalvethedualgap,Illustrationforgama,upper,lower,description,Basicparallelmachinescheduling,job4,job3,job2,job1,M2,M1,Pro_time,weight,duedate,start_time,目标2.能力约束3.自身约束,Formulation,problemformulation,StepsofLGmethod,step1.relaxationofthehardconstrainstep2.solvetheL-GdualproblemusingS-Gmethodstep3.getfeasiblesolutionusingheuristicalg0rithm,WhyusingLGmethod,GoodprimalsequenceGoodbound.,Firststeprelaxation,Dualproblem,Maxminproblem(LSS),Dualproblem,decomposition,给定将上述问题分解成N个子问题,Solvedualproblem,给定一个,将带回原问题得到关于的函数用次梯度法得到一个新的,heuristic,GetfeasiblesolutionLG-solutionisagoodprimalsolutionThesequenceisgoodbutviolatethecapacityconstrain.Theonewhocostmuchgoesfirst,soitgoeson.,Flowchartofheuristic,List按照（LGstart）K=1,i=1,Mk=0?,no,有任务在k完成吗,yes,Mk+;(k+1N),yes,SetK=k+1,Reformthelist,i+;调度下一个job,i=job_num?,re-freshstart,Refreshstart,no,end,yes,Simulationresults,eg1:12jobsand2identicalmachines;Eg2:25jobsand4identicalmachines;Result:Eg1bound=31.82withbestheuristicresult34;Eg2bound=37.74withbestheuristicresult38;,analysis,DeepintopaitheLGmultiplierWhatisthemeaningofpaiinphysicalsense?Howitactsandchangesduringtheitaration?TheLGsolutionisagoodprimalsolutionthoughnon-feasible.WhytheLGsolutionisagoodprimalsolution?,Pai(what),IttellsusHowimportantisthetimeKHowimportantisthemachineoftimekConclusionThecostofusingtheresourceoftimek,Mathematicalsense(pai),Paistandsforthecostofresourceattimek,Illustrationforpai,不同时刻的pai在整个迭代过程中的趋向,K在,Illustrationforpai,1.2.3.4.5分别代表不同的迭代时间,经过迭代pai46最终的值,Illustrationforpai,Pai!=0,Pai!=0;Howcanthesolutionofacompletelydifferentproblemgivesyouagoodprimalsolution?,原问题一定跟对偶问题很不一样,Formulation,problemformulation,Dualproblem,Myexplanation,Goodbeginningpromisessuccess!,Thanksforlistening!,
展开阅读全文