Զѧ
ACTA AUTOMATICA SINICA
1998 24 1  Vol.24  No.1 1998



Lagrangianɳڷ⻯

͡ºѫ
ժҪоLagrangianɳڷĻ̵ĵȷ.˻̵һֻ滮(MILP)ģͣͨɳɢԼֽΪһεŻ⣬ϲԭĶż⣬²⹹ɣһƷйأһȷʱֱԹ滮Ͷ̬滮.ȻӶżĽ⹹ԭĿн.ֵ֤˸÷Ч.
ؼʡLagrangianɳڷ̣ȣ̬滮.
SCHEDULING FOR BATCH CHEMICAL PROCESSES USING
LAGRANGIAN RELAXATION-BASED APPROACH
WANG ZHAOHUICHEN HAOXUNHU BAOSHENG
(System Engineering Institute,Xian Jiaotong University,Xian710049)
AbstractIn this paper,an approach based on Lagrangian Relaxation to schedule batch chemical processes is presented.The scheduling problem is modeled as a compact MILP formulation.The constraints including both discrete and continuous variables are relaxed and the problem is turned into a two-level optimization problem.The high level is the dual of the original problem,and the low level consists of two subproblems,one for batch-sizing,the other for deciding the time table.Linear programming and dynamic programming methods are used to solve the subproblems.A feasible solution is then constructed based on the solution of the dual problem.Computational results are given to demonstrate the effectiveness of the approach.
Key wordsLagrangian relaxation,batch chemical processes,scheduling,dynamic programming.
1
ǻһǳҪĹ.ɢ棬̵ĵȷǳӣNPȫģ1.Kondili״̬-(STN)̣MILPһܣ2.ڼ㸴.Shahף2ݵּ򻯼ļ3ݣԲܴӸϽ㸴.
LagrangianɳڷΪһֽŷѾɹӦϵͳ4ݺ͵ϵͳȣ5ݣºѫLagrangianɳںͶ̬滮ϵķϵͳһָΪЧĵ㷨6.STNΪ̵һָΪMILPģͣLagrangianɳڷһ̵ֻĴŵȷ.

2STN
STNһͼֽڵ㣺״̬ڵʾԭϡмƷղƷڵʾòһֻ״̬תΪһֻ״̬.ֽڵֱԲȦ;αʾ.ͼ1һ͵Ļ̵STN.


ͼ1һ͵Ļ̵״̬-(STN)
STNı
1)iı
Sii״̬ii״̬
isi״̬sڲi
isi״̬sڲi
PisiƷ״̬sĴʱ䣻
PiiĴʱ䣬kiִвi豸.
2)״̬sı
Ts״̬sϵĲs״̬sƷĲ
Smaxs״̬s.
3)豸ı
Vmaxij豸jִвiʱVminij豸jִвiʱС
Ij豸jִеĲ.
йSTN꾡ɲμף2.

3뽨ģ
о(ΪP)Ϊ
1)̵STNȫϢ
2)һȤʱΣʱοɷΪHλʱ(123H)ٶκ¼ֻܿʼĳʱεʼʱ̣½ʱt(1tH)ʼʱ̼Ϊʱt
3)ûϢԭϵϢ
4)Դ(ˮ硢)Ϣ.
ÿ̨豸ϸӦĿʼʱ䣬ʹЧ.
ȶ±
Bijttʱ̲i豸jϿʼDsttʱ̹ڲƷs
RsttʱsƷ(״̬s)ĵcsλƷsļֵ
ssλƷsλʱĴãSsttʱ״̬sеĴ
cUutʱtĵλԴuķãUutʱtԴu
UԴIOijttʱ豸jϿʼĲ
Ej豸jִеڲԵļϣEj={(Oijt,Oijt)i,iIj}
iij豸jִвiiʱsetupʱ䣻
Cijt01Bijt>0ʱΪ1Ϊ0.
ϸPɽģ£
Ŀ꺯
(1)

ϱʽеĸΪƷֵԭϼֵúԴ.
Լ
1)ƽ
(2)
2)ϴ豸Լ
(3)
(4)
3)ԴԼ
ٶԴuִвiʱһ̶һйص

BΪӦ.ʱtԴuΪ

UmaxutΪʱtϵԴu
(5)
4)Cijt
(6)
5)豸setupʱ
(7)

4Lagrangianɳڷ
ǸӦijtɳԼ(4)ͬʱһǸӦut(u,t)ɳԼ(5).Щӷֱ𹹳,кͦ.ɴ˵õɳRP
(8)

żDP
(9)
(8)ʽһ߱޹أݲƣǿɽRPΪ.
RP1
(10)
RP2
(11)
4.1RP1Ľⷨ
һԹ滮⣬õη.
4.2RP2Ľⷨ
RP2ɽһֽΪɸһ豸SP2j(±jʾ豸)
(12)
Ϊȥʾ豸±j(12)Ϊ
SP2
(13)
ʾղղʱΪ1κβsetupʱΪ0.
庯
(14)
f(t,i)ʾitʱ̿ʼִеЧ.0ܦӡH-Pr,rIJP(,r)
(15)
(16)
(17)
С(18)
g(,r)ΪJPĿ꺯ֵʾʱΪֹڦʱ̿ʼִrЧ档(15)(18)Ƴ
(19)
(20)
бʾtʱ̿ʼִrЧ.ȻSP2ֵӦΪ
SP2ŽΪOSP={tk,rk}Nk=1ͨ淽ƻOsp.
(21)
(22)
󣬿ʽȷ
(23)
4.3żDPⷨ
żôݶȷ6.ˣУ̷ֱùʽ
(24)
(25)
(26)
.hΪaΪgrad(*)ǴݶȺ.
4.4н
һ£ɶżóĽǲе.ʱΪн⣬RP2нCijt(4)(5)ʽԼRP1ٽһԹ滮⣬õĿн⣬ÿнΪŽ.򣬿ڶż⸽εϷԹ滮⣬ֱҵ.
4.5нԹ
һһн⣬ӦĿ꺯JΪֵJ*һ½.żĿ꺯J*ΪJ*һϽ.J*J*֮Ϊż϶J*-JΪż϶һϽ.Զż϶(J*-J)/J*ΪŽһ.
5ֵ
Ϊ˵㷨Чԣ2ͼ1ʾ̵ĵ⣬ף2ݽбȽ.ٶʱΪ10h4̨豸豸1豸4ֱԤͷ룬豸23ɽзӦ123.ڸϸף2.
PC486/66Turbo C.ù̵STNһļɽṹ.
һмƷAABBCEֱΪ100kg200kg,150kg100kgԭϺղƷĴ.
ñķõЧΪ2708Ӧ136kgƷ1142kgƷ2Զż϶Ϊ7.03%(1).иڵһΪţڶ͵ֱΪӦͲʼʱ.ף2ݿ֪ŽΪ2744ʵֻ1.3%.ķʱΪ53sף2еļʱΪ128s(Sun Sparcstation ).
1һĵȽ

unit 1(11000)(1362).
unit 2(2800)(3802)(4804)(3805)(4807)(3808).
unit 3(2500)(3502)(2504)(2246)(3508).
unit 4(5205)(51408).

ڶмƷBCΪ0.
㷨õЧΪ2210Ӧ116kgƷ1114kgƷ2(2).Զż϶Ϊ6.18%.ף2֪2210ΪŽ.ʱŽȻڵһмƷBCȱٴӶʹ豸ʽ͵Ե.
2ڶĵȽ

unit 1(11000)(1161).
unit 2(2480)(3802)(3804)(2786)(3808).
unit 3(2482)(4504)(4105)(4506)(4167)(3508).
unit 4(5505)(5768).

ɷԿӵԶż϶ֱΪ7.03%6.18%ʵϣнȴǳӽŽ.ֽϴԶż϶ĽṹLagrangianɳڷɵ.
㷨Чں̶ܴڽ²RP1Ч.õķԼı½ĵηøΪЧ̼ʱ.⣬ǵMILPṹ(RP1ԼAϡ)ṹⷽ㷨ļЧ.֮㷨ĽṹͷӿԿLagrangianɳڷķΪһֽʵ÷.

6
һֻLagrangainɳڷĻ̵ȵķ.ԭⱻֽΪһεŻ.ϲŻLagrangainӣ²ֱԹ滮Ͷ̬滮ȷͰʱ.лصsetupʱԼԴԼ.֤ʵ㷨Ч.
1)ȻѧĿ׼š69504008.
߼飺͡19691991ҵͨѧѧʿѧλ1994ҵڹѧԺ˶ʿѧλ.1997ϵͳоʿѧλ.оΪ̵.
ºѫ19641984ꡢ19871990ֱڸѧϺѧʿ˶ʿͲʿѧλ.ΪͨѧϵͳоڣйԶѧӦרҵίԱίԱ.оΪɢ¼̬ϵͳۣPetriӦãƻ.
19301951ҵϺͬѧϵ.Ϊͨѧϵͳоڡʿʦ.оΪɢ¼̬ϵͳӦãĿŻп㷨˻ϵͳ.
ߵλͨѧϵͳо710049
ο
1ݡKu H-M,Rajagopalan D,Karimi I.Scheduling in batch processes.Chemical Engineering Progress,August 1987,3545.
2ݡKondili E,Pantelides G C,Sargent R W H.A general algorithm for short-term scheduling of batch operations1.MILP formulation.Computers Chem.Engng.,1993,17(2):211227.
3ݡShah N,Pantelides C C,Sargent R W H.A general algorithm for short-term scheduling of batch operations2.computational issues.Computers Chem.Engng.,1993,17(2):229244.
4ݡHoitomp D J,Luh P B,Pattipati K R.A practical approach to job-shop scheduling problems.IEEE Trans.Robotics and Automation,1993,9(1):113.
5ݡGuan Xiaohong,Luh P B,Yan Houzhong,Amalfi J A.An optimization-based method for unit commitment.Electrical Power & Energy Systems,1992,14(1):917.
6ݡChen Haoxun,Chu Chengbin,Porth J-M.A more efficient lagrangian relaxation approach to Job-shop scheduling problems.In:Proc.IEEE Int.Conf.on Robotics and Automation,Japan,1995,496501.
ոڡ1996-09-16
