Scheduling Jobs with Truncated Exponential Sum-of-Logarithm-Processing-Times Based and Position-based Learning Effects
Scheduling Jobs with Truncated Exponential Sum-of-Logarithm-Processing-Times Based and Position-based Learning Effects
复制标题
DOI：
10.1142/s0217595915500268
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
Yuan-Yuan Lu-Yuan;Fei Teng;Zhi-Xin Feng
中科院分区：
文献类型：
--
作者：
Yuan-Yuan Lu-Yuan;Fei Teng;Zhi-Xin Feng
在本研究中，我们考虑在单台机器上基于截断指数对数处理时间和和基于位置的学习效果的调度问题。我们证明最短处理时间 (SPT) 规则分别对于完工时间最小化问题、作业完成时间最小化问题的 θ 次方总和以及总延迟最小化问题是最优的。对于总加权完成时间最小化问题、折扣总加权完成时间最小化问题、最大迟到最小化问题，我们根据相应的单机调度问题，在不考虑学习的情况下，提出启发式算法（也给出了这些启发式算法的最坏情况界限）。它还表明，在问题参数满足的条件下，最小化总迟到、总加权完成时间和折扣总加权完成时间的问题是多项式可解的。
In this study, we consider a scheduling problem with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects on a single machine. We prove that the shortest processing time (SPT) rule is optimal for the makespan minimization problem, the sum of the θth power of job completion times minimization problem, and the total lateness minimization problem, respectively. For the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, we present heuristic algorithms (the worst-case bound of these heuristic algorithms are also given) according to the corresponding single machine scheduling problems without learning considerations. It also shows that the problems of minimizing the total tardiness, the total weighted completion time and the discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters.