一种求解作业车间JIT调度问题的混合TS/MP算法

王荪馨; 李言; 关雄飞; 呼刚义

一种求解作业车间JIT调度问题的混合TS/MP算法

1.
西安理工大学机械与精密仪器工程学院, 西安 710048;
2.
西安理工大学高等技术学院, 西安 710082

基金项目:

陕西省教育厅重点实验室项目(11JS074)资助

详细信息

作者简介:
王荪馨(1974-),副教授,博士研究生,研究方向为先进制造技术和智能优化调度方法,wsx8280@126.com

计量
- 文章访问数: 251
- HTML全文浏览量: 30
- PDF下载量: 5
- 被引次数: 0
出版历程
- 收稿日期: 2011-12-01
- 刊出日期: 2015-06-10

A Hybrid Algorithm for Just-in-time Job-shop Scheduling Problem Based on TS/MP

1.
School of Mechanical and Precision Instrument Engineering,Xi'an University of Technology,Xi'an 710048;
2.
School of Technology,Xi'an University of Technology,Xi'an 710082

摘要

摘要: 作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。
- 作业车间 /
- JIT调度 /
- 禁忌搜索 /
- 数学规划
Abstract: A hybrid algorithm based on Tabu Search (TS) and Mathematical Programming (MP) for Just-in-timeJob-shop Scheduling Problem (JIT-JSP) is introduced in this paper,in which each operation has an earliness and atardiness cost with respect to its due date and the objective is to find a feasible scheduling minimizing the total earli-ness and tardiness costs. During search process,any individual offers the sequence orders in which the operationsshould be scheduled to the machines,and then MP method optimizes the completion times of the operations for thegenerated sequences. In order to reduce computational time,we introduce an excellent neighborhood structurebased on swap and insertion operator. The experimental results finally demonstrate the effectiveness of the proposedhybrid algorithm over a wide range of benchmarks.
- job-shop /
- JIT scheduling /
- tabu search /
- mathematical programming

HTML全文

参考文献(6)

[1]	Baptiste P，Flamini M，Sourd F. Lagrangian bounds for just-in-time job-shop scheduling[J]. Computers and Operations Re-search，2008，35:906～915
[2]	Monette J N，Devill Y，Hentenryck P. Just-in-time schedulingwith constraint programming[A]. Proceedings of the Nine-teenth International Conference on Automated Planning andScheduling[C]，2009: 241～248
[3]	Araujo R P，Santos A G，Arroyo J. Genetic algorithm and localsearch for just-in-time job-shop scheduling[A]. The IEEECongress on Evolutionary Computation[C]，Trondheim，2009:955～961
[4]	Fred G，Manuel L. Tabu Search[M]. Kluwer Academic Pub-lishers，Springer，1998
[5]	Michael P. Scheduling: Theory，Algorithms，and Systems(2nd Edition) [M]. Prentice Hall，2001
[6]	刘民，吴澄. 制造过程智能优化调度算法及其应用[M]. 北京:国防工业出版社，2008