加工时间离散可控作业车间调度问题分解方法  

作　　者：牛刚刚[1,2] 孙树栋[1] Lafon Pascal 杨宏安[1] 

机构地区：[1]西北工业大学系统集成与工程管理研究所,现代设计与集成制造技术教育部重点实验室,西安710072 [2]特鲁瓦工程技术大学LASMIS实验室,法国特鲁瓦10010

出　　处：《中国科学：技术科学》2011年第3期347-355,共9页Scientia Sinica(Technologica)

基　　金：国家自然科学基金(批准号:51075337,50705076,50705077);陕西省自然科学基础研究计划(批准号:2009JQ9002)资助项目

摘　　要：给出了加工时间离散可控的作业车间调度问题(job-shop scheduling problem with discretely controllable processing times,JSP-DCPT)基于析取图的模型及其数学描述.提出一种三步分解方法,使得JSP-DCPT可以通过求解一个作业车间调度问题(job-shop scheduling problem,JSP)以及一系列离散时间-成本权衡问题得到解决.为简化分解方法,引入时间-成本相平面描述离散时间-成本权衡问题的权衡点,并详细阐释了一种基于极限模式的集合支配理论以确定用于消减JSP-DCPT分解所得离散时间-成本权衡问题的一个上界.随后提出一种基于极限模式的集合支配分解算法EMSDDA(extreme mode-based set dominant decomposition algorithm).基于JSP标准算例FT10构造了测试算例JSPDCPT_FT10,实验仿真验证了提出的理论及分解方法的有效性.

关 键 词：作业车间调度 离散可控加工时间 时间-成本权衡 

分 类 号：TB497[一般工业技术]