一类带有deadline约束的作业车间提前/拖期调度问题研究

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。

Genetic Algorithm for Job Shop Earliness and Tardiness Scheduling Problems with Deadlines

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 algorithm(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 chromosome was processed through a three-stage decoder,to reduce the total earliness and tardiness penalties with meeting deadline constraint of jobs,in which the active decoding,chromosome repair and reverse rescheduling was operated in turn.The proposed algorithm was tested on 180 job shop scheduling problems of varying sizes and its performance was discussed.