数学规划与约束规划整合下的多目标分组排序问题研究

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

运筹学学报

数学规划与约束规划整合下的多目标分组排序问题研究

龚晶^1,*

1. 暨南大学应急管理学院，广州 510632

收稿日期:2014-11-19 出版日期:2016-03-15 发布日期:2016-03-15
通讯作者: 龚晶 tgongjing@jnu.edu.cn
基金资助:
国家自然科学基金(No. 71401062)；广东省自然科学基金(No. s2013010014179)

Integration of mathematical programming with constraint programming for multi-objective planning and scheduling

GONG Jing^1,*

1. School of Emergency Management, Jinan University, Guangzhou 510632, China

Received:2014-11-19 Online:2016-03-15 Published:2016-03-15

摘要/Abstract

摘要：

分组排序问题属于NP-难题, 单纯的数学规划模型或约束规划模型都无法在有效时间内解决相当规模的此类问题. 控制成本、缩短工期和减少任务延迟是排序问题的三个基本目标, 在实际工作中决策者通常需要兼顾三者, 并在三者之间进行权衡. 多目标分组排序问题的研究增强了排序问题的实际应用价值, 有利于帮助决策者处理复杂的多目标环境. 然而, 多目标的引入也增加了问题求解难度, 针对数学规划擅长寻找最优, 约束规划擅长排序的特点, 将两类方法整合起来, 提出一个基于Benders分解算法, 极大提高了此类问题的求解效率.

关键词: 多目标分组排序, 数学规划, 约束规划, Benders分解算法

Abstract:

Planning and scheduling, a NP-hard problem, can be viewed as a decision-making process of allocating limited resources to tasks over time with the goal of optimizing a certain objective. Neither mathematical programming nor constraint programming can solve it in the reasonable time. Minimum cost, minimum makespan and minimum tardiness are three classical objectives for this problem. The requirements from a real world application might be that several goals need to be achieved simultaneously. Based on Benders decomposition approach, this paper proposed an algorithm integrating mathematical programming and constraint programming for solving multi-objective planning and scheduling.

Key words: multiple-objective planning and scheduling, mathematical programming, constraint programming, Benders decomposition

龚晶. 数学规划与约束规划整合下的多目标分组排序问题研究[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.01.006.

GONG Jing. Integration of mathematical programming with constraint programming for multi-objective planning and scheduling[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.01.006.

参考文献

[1] Lustig I J, Puget J F. Program does not equal program: Constraint programming and its relationship to mathematical programming [J]. Interfaces, 2001, 31: 29-53.

[2] 宋继伟, 唐加福. 基于离散粒子群优化的轧辊热处理调度方法 [J]. 管理科学学报, 2010, 13(6): 44-53.

[3] 宋莉波, 徐学军, 孙延明, 等. 基一种求解柔性工作车间调度问题的混合遗传算法 [J]. 管理科学学报, 2010, 13(11): 49--54.

[4] Pinedo M. Plannig and Scheduling in Manufacturing and Services [M]. New York: Springer, 2009.

[5] Hentenryck P V, Perron L, Puget J F. Search and strategies in OPL [J]. ACM Transactions on Computational Logic, 2000, 1: 282-315.

[6] Heipcke S. Comparing constraint programming and mathematical programming approaches to discrete optimization - the change problem [J]. Journal of Operational Research Society, 1999, 50: 581-595.

[7] Rodesek R, Wallace M G, Hajian M T. A new approach to integrating mixed integer programming and constraint logic programming [J]. Annals of Operational Research, 1999, 86: 63-87.

[8] Hooker J N. A search-infer-and-relax framework for integration solution methods [J]. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems(CPAIOR), LNCS, 2005, 3524: 243-257.

[9] Kim H J, Hooker J N. Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach [J]. Annals of Operations Research, 2002, 115: 95-124.

[10] 冯欣, 唐立新, 王梦光. BAB算法中集成CPT求解job-shop调度问题 [J]. 管理科学学报, 2005, 8(3): 81-89.

[11] Benders J F. Partitioning procedures for solving mixed-variables programming problems [J]. Numerische Mathematick, 1962, 4: 238-252.

[12] Geoffrion A M. Generalized benders decompostion [J]. Journal of optimization theory and application, 1972, 10: 237-260.

[13] Hooker J N. Logic-based Methods for Optimization: Combining Optimization and Constraint Satisfaction [M]. New York: John Wiley, 2000.

[14] Jain V, Grossmann I E. Algorithms for hybrid MILP/CP models for a class of optimization problems [J]. INFORMS Journal on Computing, 2001, 13: 258-276.

[15] Harjunkoski I, Grossmann I E. Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods [J]. Computers and Chemical Engineering, 2002, 26: 1533-1552.

[16] Maravelias C T, Grossmann I E. A hybrid MILP/CP decomposition approach for the continuous time scheduling of multipurpose batch plants [J]. Computers and Chemical Engineering, 2004, 28: 1921-1949.

[17] Coban E, Hooker J N. Single facility scheduling by logic-based Benders decomposition [J]. Annals of Operations Research, 2013, 210(1): 245-272.

[18] Hooker J N. Planning and scheduling by logic-based benders decomposition [J]. Operations Research, 2007, 55(3): 588-602.

[19] Lin S W, Ying K C. A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems [J]. International Journal of Production Research, 2015, 53(4): 1065-1076.

[20] Fernandez-Viagasa V, Framinana J M. A bounded-search iterated greedy algorithm for the distributed permutation flow-shop scheduling problem [J]. International Journal of Production Research, 2015, 53(4): 1111-1123.

数学规划与约束规划整合下的多目标分组排序问题研究

Integration of mathematical programming with constraint programming for multi-objective planning and scheduling

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	高雷阜, 闫婷婷. 均衡约束数学规划问题的一类广义Mond-Weir型对偶理论[J]. 运筹学学报, 2019, 23(2): 95-103.
[2]	孙尔江. 多目标数学规划有效集的参数表示[J]. 运筹学学报, 2015, 19(3): 42-47.
[3]	中国运筹学会数学规划分会. 中国数学规划学科发展概述[J]. 运筹学学报, 2014, 18(1): 1-8.
[4]	黄正海, 林贵华, 修乃华. 变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J]. 运筹学学报, 2014, 18(1): 113-133.
[5]	黎健玲, 谢琴, 简金宝. 均衡约束数学规划的约束规格和最优性条件综述[J]. 运筹学学报, 2013, 17(3): 73-85.
[6]	唐万梅, 戎卫东. 无条件C的广义$\alpha \eta $}-单调性的判别标准[J]. 运筹学学报, 2011, 15(2): 11-18.