Bad-scenario-set Robust Optimization Framework With Two Objectives for Uncertain Scheduling Systems

Bing Wang; Xuedong Xia; Hexia Meng; Tao Li

Volume 4 Issue 1

Jan. 2017

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2017 > 4(1): 143-153

Bing Wang, Xuedong Xia, Hexia Meng and Tao Li, "Bad-scenario-set Robust Optimization Framework With Two Objectives for Uncertain Scheduling Systems," IEEE/CAA J. Autom. Sinica, vol. 4, no. 1, pp. 143-153, Jan. 2017.

Citation:

Bing Wang, Xuedong Xia, Hexia Meng and Tao Li, "Bad-scenario-set Robust Optimization Framework With Two Objectives for Uncertain Scheduling Systems," IEEE/CAA J. Autom. Sinica, vol. 4, no. 1, pp. 143-153, Jan. 2017.

Citation:

PDF( 1754 KB)

Bad-scenario-set Robust Optimization Framework With Two Objectives for Uncertain Scheduling Systems

School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China

Funds:

National Natural Science Foundation of China 60874076

National Natural Science Foundation of China 61273182

National Natural Science Foundation of China 61273040

the Shanghai Rising-Star Program 15QA1402000

More Information

Author Bio:
Xuedong Xia received his B. E. degree from the School of Physics and Electronic Electrical Engineering, Huaiyin Normal University, China, in 2013. He is currently a master student at the School of Mechatronic Engineering and Automation, Shanghai University. His research interests include production planning and scheduling (e-mail: hytcxiaxdong@163.com)

Hexia Meng received her B. E. degree from the School of Electric Power, North China University of Water Resources and Electric Power, China, in 2012. She is currently a master student at the School of Mechatronic Engineering and Automation, Shanghai University. Her research interests include production planning and scheduling (e-mail: menghx2014@163.com)

Tao Li received the B. E. degree in automation from Nankai University, Tianjin, China, in 2004, and the Ph. D. degree in systems theory from the Academy of Mathematics and Systems Science (AMSS), Chinese Academy of Sciences (CAS), Beijing, China, in 2009. From July 2009 to December 2013, he was a faculty member of AMSS, CAS. Since December 2013, he has been with the School of Mechatronic Engineering and Automation, Shanghai University, Shanghai, China, where now he is a professor. His current research interests include stochastic systems, networked control, multi-agent systems and sensor networks. He was mentioned as one of the five finalists for the Young Author Prize of the 17th IFAC World Congress, Seoul, 2008. He received the Special President Prize of Chinese Academy of Sciences in 2009, the Best Paper Award of the 7th Asian Control Conference with coauthors in 2009, the 2009 Singapore Millennium Foundation Research Fellowship and the 2010 Endeavor Research Fellowship from Australian Government. He was entitled Dongfang Distinguished Professor by Shanghai Municipality in 2012 and received National Science Found for Outstanding Young Scholars from National Natural Science Foundation of China in 2015. He is a member of IFAC Technical Committee on Networked Systems and a council member of Shanghai Association of Automation. He is a Senior Member of IEEE.(e-mail: sixumuzi@shu.edu.cn)
Corresponding author: Bing Wang received her B. E. degree in precision mechanism and precision instrument from University of Science and Technology of China in 1989, her Master degree in operations research and control theory from Shangdong University, China, in 2001, and her Ph. D. degree in control theory and control engineering from Shanghai Jiao Tong University, China, in 2005. From March 2008 to March 2009, she was a visiting scholar with the Department of Industry and System Engineering, University of Florida, USA. Before January 2011, she was a faculty member of Shandong University at Weihai, and currently she is a professor at the School of Mechatronic Engineering and Automation, Shanghai University, China. Bing Wang's current research interests include scheduling theory and algorithm, production planning and scheduling, robust discrete optimization theory and application, and health-care management and optimization. She is the author or coauthor of over 50 published papers. (e-mail: susanbwang@shu.edu.cn)
Received Date: 2015-01-23
Accepted Date: 2015-10-23

Abstract

Abstract

This paper proposes a robust optimization framework generally for scheduling systems subject to uncertain input data, which is described by discrete scenarios. The goal of robust optimization is to hedge against the risk of system performance degradation on a set of bad scenarios while maintaining an excellent expected system performance. The robustness is evaluated by a penalty function on the bad-scenario set. The bad-scenario set is identified for current solution by a threshold, which is restricted on a reasonable-value interval. The robust optimization framework is formulated by an optimization problem with two conflicting objectives. One objective is to minimize the reasonable value of threshold, and another is to minimize the measured penalty on the bad-scenario set. An approximate solution framework with two dependent stages is developed to surrogate the biobjective robust optimization problem. The approximation degree of the surrogate framework is analyzed. Finally, the proposed bad-scenario-set robust optimization framework is applied to a scenario job-shop scheduling system. An extensive computational experiment was conducted to demonstrate the effectiveness and the approximation degree of the framework. The computational results testified that the robust optimization framework can provide multiple selections of robust solutions for the decision maker. The robust scheduling framework studied in this paper can provide a unique paradigm for formulating and solving robust discrete optimization problems.
- Approximate solution,
- bad-scenario set,
- biobjective problem,
- job shop,
- robust optimization framework

FullText(HTML)

References(37)

References

[1]	W.Herroelen and R.Leus, "Project scheduling under uncertainty:Survey and research potentials, "Eur.J.Oper.Res., vol.165, no.2, pp.289-306, Sep.2005. http://www.sciencedirect.com/science/article/pii/S0377221704002401
[2]	I.Sabuncuoglu and S.Goren, "Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research, "Int.J.Comput.Integr.Manuf., vol.22, no.2, pp.138-157, Feb.2009. doi: 10.1080/09511920802209033
[3]	J.M.Mulvey, R.J.Vanderbei, and S.A.Zenios, "Robust optimization of large-scale systems, "Oper.Res., vol.43, no.2, pp.264-281, Apr.1995. http://www.sciencedirect.com/science/article/pii/S0360544212007736
[4]	P.Kouvelis and G.Yu, Robust Discrete Optimization and Its Applications. Norwell, MA:Kluwer Academic Publisher, 1997.
[5]	Z.K.Li and M.G.Ierapetritou, "Robust optimization for process scheduling under uncertainty", Ind.Eng.Chem.Res., vol.47, no.12, pp.4148-4157, May 2008. http://cat.inist.fr/?aModele=afficheN&cpsidt=20426537
[6]	A.D.Che, J.Feng, H.Chen, and C.Chu, "Robust optimization for the cyclic hoist scheduling problem, "Eur.J.Oper.Res., vol.240, no.3, pp.627-636, 2015. http://www.sciencedirect.com/science/article/pii/S0377221714005505
[7]	Z.Q.Chang, S.J.Song, Y.L.Zhang, "Distributionally robust single machine scheduling with risk aversion, "Eur.J.Oper.Res., to be published. http://www.sciencedirect.com/science/article/pii/S0377221716304453
[8]	M.Pinedo, "Minimizing the expected makespan in stochastic flow shops, "Oper.Res., vol.30, no.1, pp.148-162, Feb.1982. http://dl.acm.org/citation.cfm?id=2772472
[9]	S.D.Wu, E.S.Byeon, and R.H.Storer, "A Graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness, "Oper.Res., vol.47, no.1, pp.113-124, Jan.1999.
[10]	X.X.Lin, S.L.Janak, and C.A.Floudas, "A new robust optimization approach for scheduling under uncertainty:I.bounded uncertainty, Comp.Chem.Eng., vol.28, no.6-7, pp.1069-1085, Jun.2004. http://www.doc88.com/p-2985317973017.html
[11]	A.L.Soyster, "Convex programming with set-inclusive constraints and applications to inexact linear programming, "Oper.Res., vol.21, no.5, pp.1154-1157, Oct.1973. http://industry.wanfangdata.com.cn/dl/Detail/ExternalResource?id=gdyjs201507014%5e22
[12]	A.Ben-Tal and A.Nemirovski, "Robust solutions of uncertain linear programs, "Oper.Res.Lett., vol.25, no.1, pp.1-13, Aug.1999. http://www.sciencedirect.com/science/article/pii/S0167637799000164
[13]	D.Bertsimas and M.Sim, "Robust discrete optimization and network flows, "Math.Program., vol.98, no.1-3, pp.49-71, Sep.2003. doi: 10.1007%2Fs10107-003-0396-4
[14]	R.L.Daniels and P.Kouvelis, "Robust scheduling to hedge against processing time uncertainty in single-stage production, "Manag.Sci., vol.41, no.2, pp.363-376, Feb.1995. http://dl.acm.org/citation.cfm?id=2827855
[15]	P.Kouvelis, R.L.Daniels, and G.Vairaktarakis, "Robust scheduling of a two-machine flow shop with uncertain processing times, "ⅡE Trans., vol.32, no.5, pp.421-432, May 2000.
[16]	C.Artigues, J.C.Billaut, and C.Esswein, "Maximization of solution flexibility for robust shop scheduling, "Eur.J.Oper.Res., vol.165, no.2, pp.314-328, Sep.2005. http://www.sciencedirect.com/science/article/pii/S0377221704002425
[17]	R.L.Daniels and J.E.Carrillo, "beta-robust scheduling for singlemachine systems with uncertain processing times, "ⅡE Trans., vol.29, no.11, pp.977-985, Nov.1997.
[18]	B.Wang, X.F.Yang, and Q.Y.Li, "Bad-scenario set based riskresisting robust scheduling model, "Acta Automat.Sin., vol.38, no.2, pp.270-278, Feb.2012. http://en.cnki.com.cn/Article_en/CJFDTOTAL-MOTO201202014.htm
[19]	C.W.Wu, K.N.Brown, and J.C.Beck, "Scheduling with uncertain durations:modeling beta-robust scheduling with constraints, "Comput. Oper.Res., vol.36, no.8, pp.2348-2356, Aug.2009. http://www.sciencedirect.com/science/article/pii/S0305054808001469
[20]	P.Kouvelis, A.A.Kurawarwala, and G.J.Gutierrez, "Algorithms for robust single and multiple period layout planning for manufacturing systems, "Eur.J.Oper.Res., vol.63, no.2, pp.287-303, Feb.1992. https://utexas.influuent.utsystem.edu/en/publications/algorithms-for-robust-single-and-multiple-period-layout-planning-
[21]	T.Assavapokee, M.J.Realff, J.C.Ammons, and I.H.Hong, "Scenario relaxation algorithm for finite scenario-based minCmax regret and minCmax relative regret robust optimization, "Comput.Oper.Res., vol.35, no.6, pp.2093-2102, Jun.2008. http://www.sciencedirect.com/science/article/pii/S0305054806002735
[22]	M.A.Al-Fawzan and M.Haouari, "A bi-objective model for robust resource-constrained project scheduling, "Int.J.Prod.Econ., vol.96, no.2, pp.175-187, May 2005. http://www.sciencedirect.com/science/article/pii/S0925527304001458
[23]	R.Qing-dao-er-ji, Y.P.Wang, and X.L.Wang, "Inventory based twoobjective job shop scheduling model and its hybrid genetic algorithm, Appl.Soft Comput., vol.13, no.3, pp.1400-1406, Mar.2013. http://www.sciencedirect.com/science/article/pii/S1568494612001883
[24]	D.M.Lei, "Simplified multi-objective genetic algorithms for stochastic job shop scheduling, "Appl.Soft Comput., vol.11, no.8, pp.4991-4996, Dec.2011. http://www.sciencedirect.com/science/article/pii/S1568494611002195
[25]	A.S.Jain and S.Meeran, "Deterministic job-shop scheduling:past, present and future, "Eur.J.Oper.Res., vol.113, no.2, pp.390-434, Mar.1999. http://www.academia.edu/5906092/Deterministic_job-shop_scheduling_Past_present_and_future
[26]	C.Y.Zhang, P.G.Li, Z.L.Guan, and Y.Q.Rao, "A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, "Comput.Oper.Res., vol.34, no.11, pp.3229-3242, Nov.2007. http://dl.acm.org/citation.cfm?id=1934910.1935572
[27]	V.J.Leon, S.D.Wu, and R.H.Storer, "Robustness measures and robust scheduling for job shops, "ⅡE Trans., vol.26, no.5, pp.32-43, Sep.1994. http://citeseerx.ist.psu.edu/showciting?cid=805716
[28]	E.S.Byeon, S.D.Wu, and R.H.Storer, "Decomposition heuristics for robust job-shop scheduling, "IEEE Trans.Rob.Automat., vol.14, no.2, pp.303-313, Apr.1998.
[29]	E.Kutanoglu and I.Sabuncuoglu, "Experimental investigation of iterative simulation-based scheduling in a dynamic and stochastic job shop, J.Manuf.Syst., vol.20, no.4, pp.264-279, Jan.2001. http://www.sciencedirect.com/science/article/pii/S0278612501800467
[30]	M.T.Jensen, "Generating robust and flexible job shop schedules using genetic algorithms, "IEEE Trans.Evol.Comput., vol.7, no.3, pp.275-288, Jun.2003. http://citeseerx.ist.psu.edu/showciting?cid=789621
[31]	S.V.Mehta and R.M.Uzsoy, "Predictable scheduling of a job shop subject to breakdowns, "IEEE Trans.Rob.Automat., vol.14, no.3, pp.365-378, 1998. http://ieeexplore.ieee.org/document/678447/
[32]	M.Sakawa and R.Kubota, "Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms, "Eur.J.Oper.Res., vol.120, no.2, pp.393-407, Jan.2000. http://www.sciencedirect.com/science/article/pii/S0377221799000946
[33]	J.K.Lenstra and A.H.G.R.Kan, "Computational complexity of discrete optimization problems, "Ann.Discrete Math., vol.4, pp.121-140, Dec.1979. http://www.sciencedirect.com/science/article/pii/S0167506008708215
[34]	B.Wang, X.F.Yang, and Q.Y.Li, "Genetic simulated-annealing algorithm for robust job shop scheduling, "in Fuzzy Information and Engineering, Vol.2:Advances in Intelligent and Soft Computing, B.Y. Cao, T.F.Li, and C.Y.Zhang, Eds.Berlin Heidelberg:Springer, 2009, pp.817-827. http://www.academia.edu/16003762/Genetic_Simulated_annealing_Algorithm
[35]	L.Wang and D.Z.Zheng, "An effective hybrid optimization strategy for job-shop scheduling problems, "Comput.Oper.Res., vol.28, no.6, pp.585-596, May 2001. http://www.sciencedirect.com/science/article/pii/S0305054899001379
[36]	B.Wang, J.Liu, and Y.Y.Yu, "Scenarios based Tabu search algorithm for robust job-shop scheduling, "in The Proc.Chinese Control Conf., Xi'an, China, 2013, pp.2491-2496. http://ieeexplore.ieee.org/iel7/6621666/6639389/06639845.pdf?arnumber=6639845
[37]	J.F.Muth and C.L.Thompson, Industrial Scheduling, Englewood Cliffs, NJ:Prentice-Hall, 1963.

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(3) / Tables(3)

Get Citation

PDF

XML

Article Metrics

Article views (1057) PDF downloads(18)

Bad-scenario-set Robust Optimization Framework With Two Objectives for Uncertain Scheduling Systems

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Export File

Citation

Format

Content