A column generation approach to high school timetabling modeled as a multicommodity flow problem
详细信息 查看全文
- 作者：Á ; rton P. Dorneles ; a ; arton.dorneles@inf.ufrgs.br" class="auth_mail" title="E-mail the corresponding author ; artondorneles@gmail.com" class="auth_mail" title="E-mail the corresponding author ; Olinto C.B. de Araú ; job ; olinto@ctism.ufsm.br" class="auth_mail" title="E-mail the corresponding author ; Luciana S. Buriola ; buriol@inf.ufrgs.br" class="auth_mail" title="E-mail the corresponding author
- 关键词：Timetabling ; MILP ; Column generation ; Multicommodity flow
- 刊名：European Journal of Operational Research
- 出版年：2017
- 出版时间：1 February 2017
- 年：2017
- 卷：256
- 期：3
- 页码：685-695
- 全文大小：685 K
文摘
- class="listitem" id="list_celist0001">
- class="label">•
We model the high school timetabling problem with compactness requirements.
- class="label">•
We propose two new models using a multicommodity flow representation.
- class="label">•
We propose a column generation approach for providing lower bounds for the problem.
- class="label">•
We found tight lower bounds that can be generated faster than previous approaches.
- class="label">•
New best lower bounds were found for five from twelve well-known instances.