Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine
Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine
复制标题
DOI：
10.1016/j.ejor.2012.09.013
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
J. Qian;G. Steiner
中科院分区：
文献类型：
--
作者：
J. Qian;G. Steiner
我们考虑调度问题的学习/恶化的影响和时间依赖的处理时间在一台机器上，有或没有到期日分配的考虑。通过将它们归结为乘积矩阵上的一个特殊的指派问题，我们在近似线性时间内解决了所有这些问题。这提高了以前的算法的时间复杂度为一些调度问题，并建立了快速多项式可解性的其他几个问题。
We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.