APP下载

具有多重公共工期的单机退化工件排序

2016-01-20李士生陈仁霞孟金涛

中原工学院学报 2015年1期

李士生, 陈仁霞, 冯 琪, 孟金涛

(1.中原工学院, 郑州450007; 2.郑州航空工业管理学院, 郑州 450015)

具有多重公共工期的单机退化工件排序

李士生1, 陈仁霞1, 冯琪1, 孟金涛2

(1.中原工学院, 郑州450007; 2.郑州航空工业管理学院, 郑州 450015)

摘要:研究了需要同时确定最优工件工期和加工序列的单机排序问题。工件的加工时间是其开工时间的线性增长函数。每个工件的惩罚费用包含两部分,一部分是分配给它的工期费用,另一部分是由机器上产生的提前及延迟惩罚费用。管理者的目标为最小化所有工件的总惩罚费用。对于公共工期个数固定的情形,给出了一个多项式时间算法。

关键词:单机排序;退化工件;多重公共工期

在主流的理论排序和应用排序中,一个广泛采用的假定是工件加工时间恒定不变。然而,在火灾抢险、钢铁生产、金融管理、国防工业、紧急病房以及资源分配等许多工业工程中,任务(工件)的开工时间越晚,其相应的加工时间就越长,需要花费更多的时间和费用来完成。这类工件的加工时间依赖其开工时间的排序问题在最近的十多年里得到了广泛的关注[1-3]。

本文考虑需要确定工期分配的单机退化工件排序问题。其中,给定一些需要在一台机器上加工的工件,它们都在0时刻同时到达。每个工件有一个基本的加工时间,而实际加工时间是其开工时间的一个线性增长函数。相应地,每个工件的惩罚费用包含一个与分配给它的工期相关的费用和排序所产生的提前及延迟费用。……

登录APP查看全文