Single facility scheduling with nonlinear processing times
Single facility scheduling with nonlinear processing times
复制标题
DOI：
10.1016/0360-8352(88)90041-1
复制
发表时间：
1988-09
影响因子：
7.9
通讯作者：
J. Gupta;Sushil K. Gupta
中科院分区：
文献类型：
--
作者：
J. Gupta;Sushil K. Gupta
本文研究了一类静态单设备排序问题，其中工件的加工时间是工件开始（等待）时间的单调递增函数，目标是使所有工件完成加工的总耗时（称为最大耗时）最小.基于对问题的组合分析，给出了一般加工时间函数的精确优化算法，并将其应用于线性情况。针对非线性加工时间函数精确优化算法计算量过大的问题，提出了启发式算法。这些建议alogrithms的有效性进行了实证评估，发现表明这些启发式算法在许多情况下产生最佳或接近最佳的时间表。
This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called themakespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases.