单机成组调度问题的约束满足建模与求解方法

中国机械工程 ›› 2013, Vol. 24 ›› Issue (12): 1642-1649.

单机成组调度问题的约束满足建模与求解方法

姜锐1;陈亚绒1,2;管在林2;周宏明1

1.温州大学,温州,325035
2.华中科技大学数字制造装备与技术国家重点实验室,武汉,430074

出版日期:2013-06-25 发布日期:2013-07-11
基金资助:
国家自然科学基金资助重点项目（51035001）;国家杰出青年科学基金资助项目（50825503）；国家自然科学基金资助项目（71271156）；浙江省自然科学基金资助项目（Y6110045）
National Natural Science Foundation of China（No. 51035001, 71271156）;

National Science Funds for Distinguished Young Scholars( No. 50825503);
Zhejiang Provincial Natural Science Foundation of China（No. Y6110045）

Constraint Satisfaction Modeling and Solving Method for Single Machine Group Scheduling Problem

Jiang Rui1;Chen Yarong1,2;Guan Zailin2;Zhou Hongming1

1.Wenzhou University,Wenzhou,Zhejiang,325035
2.State Key Lab of Digital Manufacturing Equipment and Technology,Huazhong University of Science and Technology,Wuhan,430074

Online:2013-06-25 Published:2013-07-11
Supported by:

National Natural Science Foundation of China（No. 51035001, 71271156）;

National Science Funds for Distinguished Young Scholars( No. 50825503);
Zhejiang Provincial Natural Science Foundation of China（No. Y6110045）

摘要/Abstract

摘要：

为适应多品种小批量生产需求,企业普遍采用基于成组技术的混流生产,由此产生的成组调度需要平衡安装时间减少与满足交期之间的冲突关系。在分析安装时间是否依赖工件组排序、工件组能否分割加工等成组特征的基础上,以最小化加权流程时间与加权拖期为目标,构建了单机成组调度问题的约束满足模型,提出了以变量排序启发式搜索和前向约束传播相结合的求解方法。典型生产数据的实证分析表明,所提出的方法建模能力强,解的适应性好。

关键词: 成组调度, 约束满足, 启发式搜索, 约束传播

Abstract:

Mix-flow production based on group technology was adopted generally by enterprises to meet the demands of multi-variety and small batch,and a
group scheduling method was used to balance the conflict relation between setup time decreasion and delivery satisfaction.Based on the analysis of group characteristics of setup time
and processing batch size,the paper constructed a constraint satisfaction model for
single machine group scheduling with the objective of minimizing weighted flow time
and tardiness,and introduced a mix solving method with a variable and value heuristic search,and look-ahead constraint propagation.Typical empirical analysis shows the proposed method is of strong modeling capabilities and good adaptability.

Key words: family scheduling, constraint satisfaction, heuristic search, look-ahead constraint propagation

中图分类号:

F406

姜锐1, 陈亚绒1, 2, 管在林2, 周宏明1. 单机成组调度问题的约束满足建模与求解方法[J]. 中国机械工程, 2013, 24(12): 1642-1649.

JIANG Dui-1, CHEN E-Rong-1, 2, GUAN Zai-Lin-2, ZHOU Hong-Meng-1. Constraint Satisfaction Modeling and Solving Method for Single Machine Group Scheduling Problem[J]. China Mechanical Engineering, 2013, 24(12): 1642-1649.

参考文献

[1]Potts C N. Scheduling TwoJob Classes on a Single Machine[J]. Computers &. Operations Research, 1991, 18( 5) : 411-415.
[2]Webster S, Baker K R. Scheduling Groups ofJobs on a Single Machine[J]. Operations Research, 1995, 43(4) :692-703.
[3]陈亚绒[1,2],管在林[1],彭运芳[1],邵新宇[1].面向大规模定制的瓶颈成组调度启发式方法研究[J].中国机械工程,2010(8):957-962.
[4]Potts C N, Kovalyov M Y. Scheduling with Batc?hing i A Review[J]. EuropeanJournal of Operational Research, 2000,120 (2) : 228-249.
[5]Hitomi Kv Ham 1. Operations Scheduling for Group Technology Applications[J]. Annals of the CIRP, 1976,25(1):419-422.
[6]GhoshJ B. Batch Scheduling to Minimize Total Completion Time[J]. Operations Research Letters, 1994,6(5),271-275.
[7]Panwalkar S Sv Smith M L,Koulamas C P. A Heu?ristic for the Single Machine Tardiness Problem[J]. EuropeanJournal of Operational Research, 1993,70 (3) ,304-310.
[8]Liao L M, Liao CJ. A Tabu Search Approach for Single Machine Scheduling with Major and Minor Setups[J]. InternationalJournal of Industrial Engi?nee ring , Theory Applications and Practice, 2002, 9 (2) ,174-183.
[9]王秀利[1],吴惕华[2],刘磊[3].一种求解单机成组作业优化调度的启发算法[J].计算机仿真,2003,20(2):48-50.
[10]Mason AJ. Genetic Algorithms and Scheduling Problems[D]. Cambridge, University of Cam?bridge, UK, 1992.
[11]聂黎[1],高亮[1],胡译丹[1].基于前序基因表达式编程的单机成组调度算法[J].计算机集成制造系统,2007,13(11):2261-2268.
[12]Crauwels H AJ , Potts C N, van Wassenhove L N. Local Search Heuristics for Single Machine Sched?uling with Batch Set- up Times to Minimize To?tal Weighted Completion Time[J]. Annals of Op?erations Research,1997, 70,261-279.
[13]BeckJ C,Fox M S. Dynamic Problem Structure A?nalysis as a Basis for Constraint- directed Sched?uling Heuristics[J]. Artificial Intelligence, 2000 (117) ,31-81.
[14]WatsonJ P, BeckJ C. A Hybrid Constraint Pro?gramming/Local Search Approach to 'theJob?Shop Scheduling Problem[CJ/ /Conference on In?tegration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Paris, 2008,5015: 263-277.
[15]Malapert A,Gueret C, Rousseau LM. A Constraint Programming Approach for a Batch Processing Problem with Non - identicalJob Sizes[J]. Euro?peanJournal of Operational Research, 2012,221 (3) ,533-545.