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

摘要

研究一种带有学习和恶化效应,并且机器具有可用性限制的排序问题.讨论的目标函数为加权总完工时间的单机和两台机器的平行机问题.在某些实际生产过程中,工件加工时间的变化既受生产设备长时间使用,导致恶化现象的影响,也受生产设备或工人加工效率提高的影响.因此,在这种模型中,工件的实际加工时间不仅与它的所排位置有关,而且还与工件的开始加工时间有关.此外,由于机器发生故障或进行维护与保养等原因,导致其在某一区间内无法加工工件.针对某种学习和恶化效应模型下机器在任意时间段维修的单机和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/worker's 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.