摘要
针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。
This paper studied a job shop scheduling problem with due dates and deadlines in the presence of tardiness and earliness penalties. In order to solve this problem,an enhanced genetic algo- rithm（EGA） was introduced herein. EGA utilized an operation--based scheme to represent schedules as chromosomes. After the initial population of chromosomes was randomly generated, each chromo- some was processed through a three--stage decoder,to reduce the total earliness and tardiness penal- ties with meeting deadline constraint of jobs, in which the active decoding, chromosome repair and re- verse rescheduling was operated in turn. The proposed algorithm was tested on 180 job shop schedu- ling problems of varying sizes and its performance was discussed.
出处
《中国机械工程》
EI
CAS
CSCD
北大核心
2012年第15期1811-1818,共8页
China Mechanical Engineering
基金
国家自然科学基金资助项目(51075337)
