具有学习效应的平行机排序问题

摘要

针对具有学习效应的平行机排序模型,讨论了两类问题。在这一模型中,工件的实际加工时间不仅与其所在排序中的位置有关并且与其本身的学习率有关,对于在同一台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。第1类问题的目标函数是极小化提前与延误的加权和;第2类问题的目标函数是极小化提前与误工工件数的加权和。对这两类问题分别给出了多项式算法。