Ϣ
INFORMATION AND CONTROL
1999 28 2 Vol.28 No.2 1999



̵
۷˺񡡳ºѫ
ժҪ˻̵ص㡢ѵ㼰һܣܽ˽ȡõĽչʹڵ⣬ָ˽ķչ
ؼʡ̣Ʒ̣ĿḶ́ȣ
THE SURVEY OF SCHEDULING OF BATCH CHEMICAL PROCESS
LI HuifangLI RenhouCHEN Haoxun
(Institute of System Engineering, Xi'an Jaotong University*Xi'an, 710049, PRC)
AbstractThis paper describes the characteristics, difficulties and general framework of scheduling problem in batch chemical process, then summarizes the progress made and existing problems in this area during the last few years, and finauy points out the developmentg trends in the future.
Key wordsbatch chemical process, multiproduct plants, multipurpose plants, scheduling, integration
1
ڻѧҵ(Chemical Processing IndustryCPI)УоȷƷڹÿһ豸ϱӹĴŻĳЩõĻϵͳָ꣮ڲͬƷԹԴ(ԭϡ豸)ľģȵĿѰһַȥЩԴʹԼõ㣬СɢĵѾܺõؽ[1]̵ĵδܵõϺõķչΪ漰Ķ⸴Լϵʣ
ʺڴʺСƷҲֵϸߵĲƷͬʱ漰˶ʹõĵУ6%Ĵܱ[2]ɴ˿ɼҪԼ־(permanence)ԣŵеԣͨԴ豸ͬԴĹͬһֲƷҸʺϴӵĺϳɹ̣
ȥҪߵļɼָƻʱ䳤ֲܵõõľЧ棻ͬʱǵص㣬CIM()˼ļ˳о̵ȣʵԶⷽ棬һоɹ[2,534]ڵĻ̴Ъģʽ̻䣬ȵоҪ̹ҵ[3,4]̵ȵоŸոտʼгõļҾ£ģʽΪҵӦ仯гṩѡΪ˿չȵоɾ൱ἰ壮
̿ɱΪࣺƷ(multiproduct)̼Ŀ(multipurpose)̣ڶƷУеĲƷѭͬļӹ·ڶĿĹУƷܾеĲͬ·ҶԲͬĲƷвͬļӹ·һҪصǣǵʼЧϸڹ̵ȣڶƷ֮䣬ʱ估ԴΪﵽŵĿ꣬ЭԭϼѧмƷصӰ죻ԴƣͶ洢ùԴ(ˮ硢úȴˮ)ʵڼС豸άʱ䣬Ԥ[2]ȻЩرȺЭϣԴﵽŹ̵ƻ
Ľܽữ̵оҪѵ㣬ȻԵǰ̵ȵҪۡӴ˲о·
2̵оҪѵ
̲ͬɢϵͳһҪص㣬ͬʱ漰ɢ⣬ڵƺԼ磺
(1) 漰Դ븨Դ(2) ˳йص׼ʱ䣬豸ϴʱ䣬ӦеĲϴȣ(3) Ʒķ㴫ʱ䣬Ʒڴдһ̨豸һ̨豸Ҫʱ䣻(4) ͬм洢Իϵм洢ԣ(5) мƷĲȶԣ(6) ӹ·ɱ䣮
Ӷʹ̵ȵо¼ѵ.
2.1ģ
ȣ漰ԴԭϡԴм洢豸[21]Σвͬм洢ԣڲƷ豸׼͸ģϴһֲһֲת(transfer)ʱЭ[22]Ӧ·ԣЩӦڹģг֣
2.2㸴
صӰ죬紦Ľṹм洢۵ȵоݵ[5]ȫ潨ģĹģҲڵNP-hardŻ⣬ʱģָΪˣģȫ滯Ч֮Ȩ⣬̵ȼ⣮
2.3̬
Уо޵ļ½еģ豸ʱ䣬ֻһм洢(interstage storage)ȣڶڵУǼбȵĲƷһʼ֪ģȻCPIĳӦǣڵĵʱһĲƷҪԵ˶̬Ҫ
3̵
3.1ƻĲνṹ
Reklatics[5]ΪƻоκͶηڵηУͬʱƻϸĵȣƻʱ䷶ΧΪĿʱΣÿһʱָƷȷԼ󣮷ĿȷҪĲƷĿ()ԴҪ󣬿ˮƽƷ豸ķ䣬ʱڲƷʹ桢ԴûķСоһûԹ滮(MILP)[2]
ڶηУⱻΪ߲(ڻ)ƻһͲ()/⣮߲ƻʵ൱ڵηеĶʱԹ滮⣬ͲҪȷƷÿ̨豸ϴĴϸʱƷĽڻʹĳָţڶڵ֮𲢲ǺԵģĽ۶/⣬Ƶ⣮
3.2̵һ
һⶨΪеÿһ̨豸ȷÿһʱӦĸƷŻĳʵָ꣮Ի̣5.
(1)ָӦľҪһΪĳ̶ֹʱӦѭ(closed shop)ʱûԴɲƷĿеõ㣮Ǳ仯ģӦ÷ѭ(open shop)ʱֱûҪûÿӦĲƷ
(2)ƣڶƷУƷС(batchsize)Ʒ豸أƷ˳豸СожٶƷǹ̶ģʵϣɱǻ̵Ҫص㣬ҲʹøӵҪԭ֮һ
(3) ̽ṹĽṹֱӰ⣬һ˵ԷΪࣺ ٵ̨豸̣ ڲ豸̣ ۴豸(flowshop)һĴ/ϵͳͼ14ʾ.


ͼ1̨豸

ͼ2豸

ͼ3豸

ͼ4һ̡
ÿ豸ֿɸ豸֮໥ϵΪ࣬ͬ豸豸(ÿһ豸Ʒ޹صĴ)޹豸(ÿһ豸ԲͬĲƷвͬĴ)[35]ڻҪֲ/ϵͳCPIΪģ
(4)м洢ڶദУмƷĻѧȶ񣬳һĿĴ洢豸ݴ洦֮Ʒ¼ִ洢ģʽ
 м洢(Unlimited Intermediate Storage,UIS) м洢(Finite Intermediate Storage,FIS) ûм洢(No Intermediate Storage,NIS) ȴ(Zero Wait,ZW) ޵ȴ(Finite Wait,FW)
Ĵ洢Դ洢豸ĿԴ洢ߴģNISZWFWģʽУ֮޴洢UISFISNISFWģʽУһƷһ̨豸ϴɺ󣬿ݴڸ豸УZWģʽУ豸УмƷȶʱӦZW洢ԣõ̵Ĵ洢ԣӦϼֲԵϣϵмƷ洢(Mixed Intermediate Storage,MIS)
(5)Ŀ꣺һ࣬һǻھָ꣬һǻָģڶȽṹУ߲ƻԭϵķ䣬ûھõĿ꺯ͲĵȣûܵĵĿ[10]
ھõĵĿҪУ
 Сɱã汣ַüƷõȣ һֲƷһֲƷлĸ׼С ڲƷֵܼȥã
ܵĵĿҪУ
 вƷҪʱ伴makespanΪСʹ̵Դ󣻢 вƷƽʱ(flowtime,ƷȫͨҪʱ)С ƽӳʱ(tardiness)СӳʱڲƷʱ뽻֮ֻȡֵ ӳʱС
ܵ˵̵ࣺһ̶/⣬һɱĵ⣮
3.3ǰ̵ȵҪо
Ʒ̶ΪɣʱȷƷӹĴ򣻶˳ʱȷÿƷ豸ϴĿʼʱ䣮ɱ䣬򲻽ҪȷʱҪȷƷ
һԼŻ⣬NP_ȫԣûһЧĵ㷨һĿ꺯ĵ[20]ֻںĵ´ŽЧ磺еUISNISZWmultiproduct⣬Ŀʹmake-spanС[2,5,10]о̵ʱǳѰձһ㷨[8,9]⣬ͨԲͬʵļ裬оĳµ㷨ȷ㷨[6,7,11,12,21]ƽ㷨[1320]
3.3.1Ʒ̵
вͬϵͳص㣬Ȼƣر𵱲Ʒ̶ʱˣоһļೣ÷Ż/ŻڻеõӦã
ŻԹ滮(MILP)֧(BAB)ǳǽʹõģPekny[11]MILPڲƷһȷĲ㷨Pekny[12]BABһԴ޵Ļ̣תΪԴԼ⣻Rajagopalan[21]Ծлм洢ԡ㴫ʱ估˳йصsetupʱĴжƷ/̽оһϵмʱѭϵǣЩöٷֻڽСģ⣮
/Զȡ˼ʱ䣮㷨ǻҾжʽʱ䣬һɷΪࣺһǽһõ˳򼯣Ȼٴѡõ˳һһ˳ʼȻѭظֱٸƣ乲ǾӦ豸UISNIS/ZWflowshopľȷ[2]Ӧ÷棬ͳCDRAESڻеõӦ[2,5]Muiser[13]о˵еĶƷ̣һе㷨ϴʱ估Ʒ豸ķԼ/ȱ㷨ų̶Ȳȷ
Żģ˻𷽷ڵĿŻ⣬ǻMonte-carloϵͳģ⣮ģ˻𷽷ΪNP-ȫṩһƽ⣬ѱڻ̵ȣDas[14]ڼеȵģ˻𷽷ԶƷ̽оģ˻þ(Idle Matrix Search,IMS)UISNISZWFISMISм洢ԣĿʹmakespanΪС
ʵϣϷӦʱǽģΪʽǻMILPBABģڻBABУ½ļʽ[12]Ϊضķ֧
3.3.2ĿĹ̵
ڶƷ̵УҪ漰ʱķ䣬޴豸ѡڶĿĹУȴܸӣΪƷһڶ̨豸ϽУҳҪƷɱ䣮ȷÿĿʼʱͬʱҪȷ豸ƷڶĿĹ̵ȵоҪڶڵȣԶԶƷ룮оMILPBAB
Wellon[6,7]о˵һƷ⣬ǶĿĹ̵ȵҪ⣮߲ͨԵķ˵豸ɱ·ߵҪ棬MINLP˵ȵŽ⼯"·"ĸѰ·ϵķKondili[8]״̬(state-task network,STN)һĻ̣MILP˶ĿĹ̵һģͣSTNˡrecipe networkеĲԣиǿıȷرʾ⸴ӵĴ磮ڵ㣺״̬ڵڵ㣬״̬ڵʾԭϣмƷղƷڵʾòһֻ״̬תΪһֻ״̬ԲƷ豸Ͽʼʱ䣬仯ĲƷƷڸ״̬ĵĴ洢Ϊ߱豸ԭ(мƷ)ƽ⣬ʼڼԭϵƣ豸ϣԴ(磬ȴˮ)/ƣ豸ϴʱԼ˽ģͨ롰洢񡱵ĸ˴洢豸ĹƷ豸ݴ⣻ͨԴʵֽ(STNı)˹̽ṹĸԼʱʾΪķֶκ˴ʱڲƷShan[9][8]ܣ4ּ򻯵ļ㼼
ЩУҪ֮һʱHadson[32]оһʳƷӹ̣ù漰׼ȴ3׶ΣҪɵʼȴ֮ĵȴʱ䲻ܳ30ӣǶÿҪӹʳƷеȣҪʳƷļӹʱɣиʳƷӹȼʱ䵹Ƶķõ˽ϺõĿн⣮
Ӧó棬Egli[22]ڶƷ/Ŀ̶ڵȵļSRSBP,ȷһƷʱĳЩضҪ󣬲ʹƷáתüԴСóͨһض·ϵп˳ĿѰŵȣʵBABܴ6ֲƷ20̨豸ƻʱ60ģ⣮
3.4ơȽصļ
(1) ڹƽ׶οǵ
ڻУرǶƷУ໥ģƽ׶ԤȵӰ죬йصԼϵͳƿɴٹ̵Ͷʷã豸ʣBirewar[23]һ˼ÿһһ̨豸ĶƷ̣UISZW£ΪʹСоЧĵģͣЩȲԵļ򻯵Լϵͳ⣮
(2) 
ڸӵУ㷨ͼоĳЩ⣬˽ʺĳЩضṹģͼ裮ʵǶ̬ġӵģб仯ĽṹĿ꣬еȵжϣѶ϶ʵʵ̷ĳһ㷨ı׼ʽΪʵӦãÿһӦӲ.
(a) Ӧִĵ㷨(ȷ㷨)
(b) Ӧ˵ĸԤʹײظ޸ģ
[2]һֽϵͳINTSPAKرڶƷ̣ûһ㴦豸磬ʽŵ㷨ԶDockx[33]CPIȵSKYEϵͳҪڶڵȣSKYE＼һȹƽ̨TTP-SΪͼνߣֹԶȣ
(3) ȵߵ
̾һ̶ȵĿɱ(variability)[24]ʵиֹ̲ܷ仯(豸ʱ仯Դ豸ϣƷ䷽(recipe)ȷԭ仯)ߵĵȥָʹȴʱ䡢Ʒ(work-in-process)ӣ豸ʡƷܿܽͣΪҪʵԵȽߵأCott[24]һ֡Ԥ޸ġ㷨ӵǰĲȥ̵ĽǰƶȲƷĿʼʱ䣬Ẓ̇Djavdan[25]м洢붯̬ģоһ/Ϲ̵ߵ⣮Ishii[26]һߵϵͳܣݵı仯޸ʱռ䣬㹻ⲿ㷨̬޸еĵȣHuercio[27]һӦ(Reactive Schedule)㷨뼯ɵУ˸߲Ͳ˳֮Ŀȱʽʼʱı仯豸ط䣮
(4) ̵ļ
ȥǽ̵ĴڷֿĻоڼ棬ȡ˺ܺõĳɹڹָĵ߾в֪ͬʶԵоʱĳЩδܳһʵԼ[31]ģƫƵʱģʱʹϵͳʵӦʱڳΪӦоһͨùߣ̵֧ڣӹ̡豸ƴĳƣŵȵ߲[29]Cott[28]о˼̼ƻ̿ƵļϵͳЭƻƼͨߡصȣʵϢӿƼƻķǲ˷еĿɱԣCrooks[29]е3ͨ(ȡ̺ϳ)һγһCIMϵͳַеCAPS(̺ϳ)ϵͳһԭܹ[30]Brettle[31]һ桢ơһĹߣھϩĲԱѵ
3.5ʵӦ
̵ȵоۣضģͼ裬ӦʵУCrooks[30]һơȡһCAPSϵͳһԭܹHodson[32]һʳƷӹУ˽ϺõĿеȣOrcun[34]һȾУѧ滮ŵȣ豸ʱ仯
4뽫ķչ
ͨԻص㡢ĿܼⷽķԿȫ潨ģ൱ӣΪˣΪ¼濪չо洦ģ
(1) STNһ̽нģ󣬵ɱʾΪһӵMILP⣬ⷽϿɴ¼̽(a)ĸԣоʽ˹ܵķ⣻(b)ɳ۷Ϊһֽŷϵͳ[36]ϵͳ[37]ѵõӦã̵[38]оŸոտʼдһ룻(c)Ŵ㷨ģ˻𷽷о̵ȵ·罫ǽʹãȡ̣ɵõȫԣܱ֤ٶȣ(d)L.A.Zadehܼ()˼[39]Ԫ硢ģ߼Ŵ㷨лɣָ˼̲ȷȷصӰʵֿС³ͳɱⷽ˼ƣڽ̵ȵļ㸴Լ̬Եѵ⣮
(2) оûпǵϲ(ƻ)֮ĹϵʵϣƻӰ죬ң̵ص㣬гԴȵӰȵЧԣΪˣŵĵӦۺϿеĸأ
(3) ڽȷ棬˹ܡ㷨漼ϣʽȻƣͨܶĵ㷨ںԱжϾЧʣеĶ̬仯ʵʱ⣮оӦڣ(a)߷ٶȣ(b)ƸЧ˻ӿڣ
(4) Уھ̬ȷļоģʵУԹⲿڲ仯ʱģյ¶ض豸ϵȣЩҪʵʱضԵȽеͼأʹⲿı仯ʧС
(5) Ϊʵ̵ȫԶҪһּɻķ̵̵ָơлؽоĲ㣮Ϊˣо֪ʶϵķǺģ
(6) κεⶼҪӦ֧֣һЧĵ֧ӦȷʵʵĵȻõ˻ӿڣۺϹơƻȽʵʱصصĹܣоЧĵ֧ǵӦʵҪڣ
߼飺۷Ů32꣬ʿоΪɢ¼ϵͳ̵ۣأ
˺У53꣬ڣʿʦоΪܿ뷽ϵͳȣýCSCWӦã
ºѫУ35꣬ڣоΪɢ¼ϵͳۣPetriӦãƻȵȣ
ߵλͨѧϵͳо710049
5
ڻУǷǳӶҪ⣮һоһ㷨͸µ㷨һɹһоӦڴŻʽ㷨ԴƷӹ̼ԼĴģ⣮ΪˣͳĵȷܷϣַܵƣΪȵļ㸴⣬һµ;ԹеĶ̬صӰ죬ȵߵؼȵļɵ㷨ʵӦãод𲽽׶Σһ棬ͼΣߵʵʹ̵ӦԾкܴǱ
ο
1 Baker K R. Introduction to Sequencing & Scheduling.Wiley, New York,1974
2 Ku H-M, Rajagopalan D, Karimi I. Scheduling in Batch Process.Chem.Engng.Prog, 1987, August, 3545
3 ̹ҵCIMSԶǱ1997, 24(3):5862
4 ұCIMSƻ/ϵͳԶǱ1997, 24(6):5256
5 Reklaitics G V. Review of Scheduling of Process Operations. AICHE Symp.Ser., 1982, 78(214):119132
6 Wellons M C, Reklaitics G V. Operational Scheduling Generation for a Single-product Line-I.Problem Formulation. Computers Chem. Engng. 1987, 13(1/2):201212
7 Wellons M C, Reklaitics G V. Optimal Scheduling Generation for a Single-product Line-II. Identification of Dominant Unique Path Sequences. Computers Chem.Engng.1989, 13(1/2):213227
8 Kondili E, Pantelides C C, Sargent R W H. A General Algorithm for Short-term Scheduling of Batch Operations-I. MILP Formulation. Computers Chem. Engng, 1993, 17(2):211227
9 Shah N, Pantelides C C, Sargent R W H. A General Algorithm for Short-term Scheduling of Batch Operations-II. Computational Issues. Computers Chem. Engng, 1993, 17(2):229244
10Rechard S H M. Chemical Process Structure and Information Flows. Butterworth Publishers, Boston, U.S.A. 1990, 241299
11Pekny J F, Miller D L, Mcrae G J. An Exact Parallel Algorithm for Scheduling When Production Costs Depend on Consecutive System States. Computers Chem. Engng, 1990, 14(9):10091023
12Pekny J F, Miller D L, Kudva G K. An Exact Algorithm for Resource Constrained Sequencing with Application to Production Scheduling under an Aggregate Deadline. Computers Chem. Engng, 1993, 17(7):671682
13Muiser R F H, Evans L B. An Approximate Method for the Production Scheduling of Industrial Batch Processes with Parallel Units. Computers Chem.Engng, 1989, 13(1/2):229238
14Das H, Cumming P T, Levan M D. Scheduling of Serial Multiproduct Batch Process Via Simulated Annealing. Computers Chem. Engng, 1990, 14(12):13511362
15Wiede W Jr, Kuriyan K, Reklaitics G V. Determination of Completion Times for Serial Multiproduct Processes-I. A Two Unit Finite Intermediate Storage System. Computers Chem. Engng, 1987, 11(4):337344
16Wiede W Jr, Reklaitics G V. Determination of Completion Times for Serial Multiproduct Processes-II. A Multiunit Finite Intermediate Storage System. Computers Chem. Engng, 1987, 11(4):345356
17Wiede W Jr, Reklaitics G V. Determination of Completion Times for Serial Multiproduct Processes-III. Mixed Intermediate Storage System. Computers Chem. Engng, 1987, 11(4):357368
18Ku H-M, Karimi I. Completion Time Algorithm for Serial Multiproduct Batch Processes With Shared Storage. Computers Chem. Engng, 1990, 14(1):4969
19Carlson E C, Felder R M. Simulation And Queuing Network Modeling of Single-product Production Campaigns. Computers Chem. Engng, 1992, 16(7):701718
20Havla N, Strmacnik S, Cernetic J. Scheduling of Batch Digesters According to Different Control Targets and Serving Limitations. Computers Chem. Engng, 1993, 17(7):739750
21Rajagopalan D, Karimi I A. Completion Times in Serial Mixed-storage Multiproduct Processes with Transfer and Set-up Times. Computers Chem. Engng, 1989, 13(1/2):175186
22Egli U M, Rippin D W T. Short-term Scheduling for Multiproduct Batch Chemical Plants. Computers Chem. Engng, 1986, 10(4):303325
23Birewar D B, Grossmann I E. Incorporating Scheduling in the Optimal Design of Multiproduct Batch Plants. Computers Chem. Engng. 1989, 13(1/2):141161
24Cott B J, Macchietto S. Minimizing the Effects of Batch Process Variability Using On_line Schedule Modification.Computers Chem. Engng, 1989, 13(1/2):105113
25Djvadan P. Design of an On-line Scheduling Strategy for a Combined Batch/Continuous Plant Using Simulation. Computrs Chem. Engng. 1993, 17(5/6):561567
26Ishii N, Muraki M. A Generic Framework for an On-line Scheduling and Control System in Batch Process Management. Computers Chem. Engng. 1997, 21(11):12911310
27Huercio A, Espuna A, Puigjaner L. Incorporating On_line Scheduling Strategies in Integrated Batch Production Control. Computers Chem. Engng, 1995, 19, Suppl., 609614
28Cott B J, Macchietto S. An Integrated Approach to Computer_aided Operation of Batch Chemical Plants. Computers Chem. Engng, 1989, 13(11/12):12631271
29Crooks C A, Kuriyan K, Macchietto S. Integration of Batch Plant Design, Automation, and Operation Software Tools. Computers Chem. Engng, 1992, 16, Suppl, 289296
30Crooks C A, Evans S F, Macchietto S. An Application of Automated Operating Procedure Synthesis in the Nuclear Industry. Computers Chem. Engng, 1994, 18, Suppl,385389
31Brettelle D, Chua E S, Macchietto S. Simulation and On-line Scheduling of a PVC Process for Operator Training. Computers Chem. Engng, 1994, 18, Suppl, 547551
32Hodson A, Muhlemann A P, Price D H R. A Microcomputer Based Solution to a Practical Scheduling Problem. J.Opl. Res.Soc., 1985, 36(1):903914
33Dockx K, Boeck Y D, Meert K. Interactive Scheduling in the Chemical Process Industry. Computers Chem. Engng, 1997, 21(9):925945
34Orcun S, Discioglu A, Altinel I K, Hortacsu O. Scheduling of Batch Process: An Industrial Application in Paint Industry. Computers Chem. Engng, 1997, 21, Suppl, 673678
35Lawler E L, Lenstra J L, Rinnooy Kan A G H, Shmoys D B. The Complexity of Sequencing & Scheduling. 1985, Rep. BS-R8909, Centre for Mathematics and Computer Science. 78
36Lun P B, Hoitomp D J, Max E, Pattipati K R. Scheduling Generation and Reconfiguration for Parallel Machines. IEEE Trans. on Robotics and Automation. 1990, 6(6):687696
37Guan Xiaohong Lun P B, Zhang Lan. Nonlinear Approximation Method in Lagrangian Relaxation-based Algorithms for Scheduling. IEEE Trans.on Power Systems. 1994, 10(6):772778
38͵ȣLagrangianɳڷ⻯⣮Զѧ1998, 24(1), 18
39Zadeh L A. Fuzzy Logic,Neural Network,and Soft Computing.Communications of the ACM.1994,37(3):7783
1998-07-15ո
