摘要
针对等待时间受限的流水车间调度问题,分析了等待时间上限与可行解的解析关系以及目标函数的特殊性质,以此为基础,提出了一种启发式算法。算法采用贪婪与插入相结合的启发式规则构造工件加工序列,通过递归回溯解消其等待时间受限约束。仿真实验表明,该启发式工件排序规则在等待时间约束较紧或问题规模较大时,较其他几种常用排序规则具有更好的效果。
This paper focuses on flowshop scheduling with limited waiting times. Analytical relation between the upper bound of waiting times and feasible solutions is analyzed and certain property of the objective function is obtained, based on which a heuristic algorithm is proposed. The algorithm firstly sequences jobs by a heuristic rule combining greed with insertion, and then solves the violated waiting time constraints using recursive backtracking. Emulating experiments show that the proposed heuristic rule is superior to some common-used sequencing rules, especially when the limited waiting time constraints are tighter or the problem scale is larger.
出处
《管理学报》
CSSCI
2009年第10期1335-1339,共5页
Chinese Journal of Management
基金
国家自然科学基金资助项目(70771008
70371057)
关键词
流水车间调度
等待时间受限
启发式算法
排序规则
flowshop scheduling
limited waiting times
heuristic algorithm
sequencing rule
