不确定彩排时长下节目调度的鲁棒优化

doi:10.15960/j.cnki.issn.1007-6093.2020.03.006

运筹学学报 ›› 2020, Vol. 24 ›› Issue (3): 77-86.doi: 10.15960/j.cnki.issn.1007-6093.2020.03.006

不确定彩排时长下节目调度的鲁棒优化

仲维亚^*, 施益媚

上海大学管理学院, 上海 200444

收稿日期:2018-05-18 发布日期:2020-09-05
通讯作者: 仲维亚 E-mail:wyzhong@i.shu.edu.cn
基金资助:
国家自然科学基金（Nos.11301327，11571221，11871327）

Robust optimization of rehearsal scheduling under uncertain duration

ZHONG Weiya^*, SHI Yimei

School of Management, Shanghai University, Shanghai 200444, China

Received:2018-05-18 Published:2020-09-05

摘要/Abstract

摘要： 实际节目彩排调度中，节目的表演时长受内外因素影响，具有不确定性。为了合理调度所有节目，控制演员的空闲时间，使得演员的总等待成本最小，采用了鲁棒优化方法进行研究。首先，建立了节目彩排调度的确定型模型；进一步，考虑节目表演时长的不确定性，采用有界区间描述节目表演时长并考虑决策者风险偏好，在确定型模型的基础上构建区间型两阶段鲁棒优化模型；接着，将鲁棒优化模型转化为0-1混合线性规划模型；最后，采用Matlab进行数值实验，结果表明决策者越偏好规避风险，演员的总等待成本越大。

关键词: 节目彩排调度, 不确定表演时长, 鲁棒优化, 对偶规划

Abstract: In a dress rehearsal, the duration of a program which is affected by internal and external factors, is uncertain. A robust optimization method is adopted to schedule the programs to minimize the total waiting cost of actors. A deterministic dress rehearsal model is first proposed. Then, based on the above deterministic model, a two-stage robust optimization model is built, considering the uncertainty of the programs. durations and the risk preference of decision makers. Thirdly, the robust optimization model is converted into a 0-1 mixed linear programming. At last, numerical experiments are carried out by Matlab, and the results show that the actors' waiting cost increases with the decreasement of decision makers' risk preference.

Key words: rehearsal scheduling, uncertain rehearsal duration, robust optimization, duality programming

中图分类号:

O221.1
O224

仲维亚, 施益媚. 不确定彩排时长下节目调度的鲁棒优化[J]. 运筹学学报, 2020, 24(3): 77-86.

ZHONG Weiya, SHI Yimei. Robust optimization of rehearsal scheduling under uncertain duration[J]. Operations Research Transactions, 2020, 24(3): 77-86.

参考文献

[1] Cheng T C E, Diamond J E, Lin B M T. Optimal scheduling in film production to minimize talent hold cost[J]. Journal of Optimization Theory and Applications, 1993, 79(3):479-492.
[2] Norström A L, Tufekci S. A genetic algorithm for the talent scheduling problem[J]. Computers and Operations Research, 1994, 21(8):927-940.
[3] Qin H, Zhang Z Z, Lim A, et al. An enhanced branch-and-bound algorithm for the talent scheduling problem[J]. European Journal of Operational Research, 2016, 250(2):412-426.
[4] Bomsdorf F, Derigs U. A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem[J]. Operation Research Spectrum, 2008, 30(4):751-772.
[5] Sakulsom N, Tharmmaphornphilas W. Scheduling a music rehearsal problem with unequal music piece length[J]. Computers and Industrial Engineering, 2014, 70:20-30.
[6] 镇璐, 刘彬, 汪文成. 混合时长下节目彩排的调度优化[J]. 系统管理学报, 2017, 26(5):850-856.
[7] 孙华. 基于鲁棒优化的城市交通网络设计模型与算法研究[D]. 北京:北京交通大学, 2014.
[8] 万波, 陈琴. 不确定需求下基于鲁棒优化的层级设施选址模型[J]. 统计与决策, 2018, 33(6):57-61.
[9] 彭春, 李金林, 王珊珊, 等. 多类应急资源配置的鲁棒选址-路径优化[J]. 中国管理科学, 2017, 25(6):143-150.
[10] 许晓晴, 张宗明, 林军, 等. 基于后悔值准则的个性化产品鲁棒调度[J]. 工业工程与管理, 2017, 22(5):94-101.
[11] 赵昊天, 贾传亮, 宋砚秋, 等. 不确定需求下航空超售问题的鲁棒优化研究[J]. 中国管理科学, 2013, 21(s1):98-102.
[12] 邓爱民, 聂治坤, 刘利国, 等. 不确定性供应链的鲁棒优化研究综述[J]. 统计与决策, 2009, 24(21):160-162.
[13] 李惠, 蒋大奎. 手术持续时间不确定的手术排程鲁棒优化[J]. 工业工程与管理, 2012, 17(5):126-130.
[14] 李玉强. 鲁棒线性优化若干模型研究[D]. 青岛:山东科技大学, 2009.
[15] Charalambous C, Conn A R. An efficient method to solve the minimax problem directly[J]. SIAM Journal on Numerical Analysis, 1978, 15(1):162-187.
[16] 刘琳, 谷寒雨, 席裕庚. 加工时间不确定的just-in-time单机鲁棒调度[J]. 控制与决策, 2007, 33(10):1151-1154+1159.
[17] Bertsimas D, Sim M. The price of robustness[J]. Operations Research, 2004, 52(1):35-53.
[18] Bertsimas D, Sim M. Robust discrete optimization and network flows[J]. Mathematical Programming, 2003, 98(1/3):49-71.
[19] 姚恩瑜, 何勇, 陈仕平. 数学规划与组合优化[M]. 杭州:浙江大学出版社, 2001.
[20] 张德喜, 赵磊生. MATLAB语言程序设计教程[M]. 北京:中国铁道出版社, 2010.
[21] 刘浩. MATLAB R2012a完全自学一本通升级版[M]. 北京:电子工业出版社, 2013.

不确定彩排时长下节目调度的鲁棒优化

Robust optimization of rehearsal scheduling under uncertain duration

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	江波, 朱喜华. 基于横截面回归和Fama-MacBeth估计的鲁棒投资组合优化问题研究[J]. 运筹学学报, 2021, 25(3): 133-146.
[2]	耿晓路, 童小娇. 分布鲁棒机会约束优化问题的研究[J]. 运筹学学报, 2020, 24(1): 115-130.
[3]	王峰, 刘三阳. 鲁棒优化中的Pareto有效性[J]. 运筹学学报, 2018, 22(4): 141-147.
[4]	梁锡坤, 徐成贤, 郑冬. 鲁棒投资组合选择优化问题的研究进展[J]. 运筹学学报, 2014, 18(2): 87-95.