NP困難排序問題數(shù)學(xué)規(guī)劃松弛算法研究.pdf

1、同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系博士學(xué)位論文NP困難排序問題數(shù)學(xué)規(guī)劃松弛算法研究姓名：張峰申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：組合最優(yōu)化指導(dǎo)教師：濮定國(guó)唐國(guó)春20051001AbstraetAbstractInthispaperthealgorithmsofmathematicalprogrammingrelaxationforNPhardproblemshavebeendiscussedSchedulingwithrejectionandscheduling、

2、析tllcontrollableprocessingtimeshavebeenresearchedInchapter1，wesummarizeresultsofmathematicalprogrammingrelaxationsinscheduling，includinglinearprogrammingrelaxations，c沁nvexquadraticprogrammingrelaxationsandsemidefinitepro

3、grammingrelaxationsforsinglemachineproblem1吲∑w，0、lb嬲馴∑w夕0、l婦reclZwG、llrHarecl∑wFj、llrjprecpmtnl∑wfCj，parallelmachinesproblemRlroIEwFj、Rlrj矽mtnlEwFj、PI，=『∥訓(xùn)∑蝸andcontrollableprocessingtimesproblemRlcptl∑wjCjInchapter2，west

4、udyschedulingwithrejectionInsection1，wegivedifferent01decisionvariableswhichdecidejobisrejectionoracceptedWepresentseveralapproximationalgorithmsoflinearprogrammingrelaxations，including3一approximationalgorithmforprobleml

5、I吲∑心ej“t“Tjd_q，4approximationalgorithmand2e／(e1)p3165)approximationalgorithmforproblem1rej，precI∑心eJ∑aje$_q，and(3壓)approximationalgorithmforproblemllrej，prec，rjJ∑心勺∑，Es吩qInsection2，weobtain2一approximationand3／2approximat

6、ionalgorithmforproblemll吲∑心巳∑，舒％qbyusingconvexquadraticprogrammingrelaxationandconvexprogrammingrelaxationand2approximationalgorithmforproblemllrej，，：，IEjdej∑，es—qbyusingconvexquadraticprogrammingrelaxationInchapter3，wes

7、tudyschedulingwithcontrollableprocessingtimesInsection1，wediscussparallelmachinesproblem尸I咖一cpt，pratnl∑勺‘c『讎Weobtain2jlapproximationand1583approximationalgorithmbyusinglinearprogrammingrelaxationsMeanwhilewediscussproble

8、mllcpt，precl∑c／j∑■qWeobtainjIji4一approximationalgorithmbyusinglinearprogrammingrelaxationsInsection2，wediscussproblemRldis—cpt，‘，√∑∑q，／0∑％qandproblemRcpt，訓(xùn)iIj=l』l∑∑cj√0∑wqWeobtain2approximationalgorithmand3approximationi