机器具有可用性限制的加权总完工时间问题  

Scheduling problems with availability constrain to minimize total weighted completion time

作　　者：崔苗苗[1] 赵玉芳[1] 王松丽[1] 

机构地区：[1]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2012年第2期157-163,共7页Journal of Shenyang Normal University:Natural Science Edition

基　　金：辽宁省教育厅科学研究资助项目(2008z192)

摘　　要：研究一种带有学习和恶化效应,并且机器具有可用性限制的排序问题。讨论的目标函数为加权总完工时间的单机和两台机器的平行机问题。在某些实际生产过程中,工件加工时间的变化既受生产设备长时间使用,导致恶化现象的影响,也受生产设备或工人加工效率提高的影响。因此,在这种模型中,工件的实际加工时间不仅与它的所排位置有关,而且还与工件的开始加工时间有关。此外,由于机器发生故障或进行维护与保养等原因,导致其在某一区间内无法加工工件。针对某种学习和恶化效应模型下机器在任意时间段维修的单机和2台机器的平行机的某些情况,分别给出了拟多项式时间动态规划算法,分析了算法复杂性,并给出相应数值例子表明算法的有效性。This paper studied the scheduling problems with a learning and deteriorating effect and an availability constraint.The objective function is the total weighted completion time problems of the single and two parallel machines.In some real production situations,the processing time of a job changes due to either job deterioration over time or machine/workers learning through experiences.So that in this model,the processing time of jobs is related with their positions and starting time in a sequence;Moreover,the machine could be unavailable for a specified period by periodic machine breakdown or maintenance activity.We consider the total weighted completion time have polynomial optimal solutions under reversed order solutions.The dynamic programming algorithm are provided for the machine maintenance at any time,respectively.We analyzed the complexity of algorithms and show the efficiency of algorithm by numeral example.

关 键 词：排序 学习效应 恶化效应 机器可用性限制 动态规 

分 类 号：O223[理学—运筹学与控制论]