A Hybrid Algorithm for Just-in-time Job-shop Scheduling Problem Based on TS/MP
-
摘要: 作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。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.
-
Key words:
- job-shop /
- JIT scheduling /
- tabu search /
- mathematical programming
-
[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
点击查看大图
计量
- 文章访问数: 251
- HTML全文浏览量: 30
- PDF下载量: 5
- 被引次数: 0