Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time
Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time
复制标题
单机调度，以最小化总凸资源消耗，并限制总加权流时间
DOI：
10.1016/j.cor.2011.05.026
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
Ming-Zheng Wang
中科院分区：
文献类型：
--
作者：
Ji-Bo Wang;Ming-Zheng Wang
在本文中，我们考虑了单机排序问题，其中一个作业的加工时间用一个凸递减资源消耗函数来描述。目标是在总加权流时间的约束下最小化资源消耗总量。对于任意的作业序列，都可以得到最优的资源分配。一般问题的计算复杂性仍然是一个悬而未决的问题，但我们提出并分析了一些可以用多项式时间算法求解的特殊情况。对于一般问题，导出了几个支配性质和一些下界，并利用它们加快了求解该问题的分枝定界算法的消元过程。文中还提出了一种启发式算法，通过计算实验表明，该算法在获得近似最优解的过程中具有较好的性能。结果表明，该启发式算法对最优解的平均百分比误差小于3%。
In this paper, we consider single-machine scheduling problem in which processing time of a job is described by a convex decreasing resource consumption function. The objective is to minimize the total amount of resource consumed subject to a constraint on total weighted flow time. The optimal resource allocation is obtained for any arbitrary job sequence. The computational complexity of the general problem remains an open question, but we present and analyze some special cases that are solvable by using polynomial time algorithms. For the general problem, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. The results show that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.
登录
查看更多内容
DOI：
10.1016/j.cor.2010.03.012
发表时间：
2010-12
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
D. Shabtay;Yisrael Itskovich;Liron Yedidsion;Daniel Oron
通讯作者：
D. Shabtay;Yisrael Itskovich;Liron Yedidsion;Daniel Oron
DOI：
10.1287/moor.15.4.736
发表时间：
1990-10
期刊：
Math. Oper. Res.
影响因子：
--
作者：
C. Monma;A. Schrijver;M. Todd;V. Wei
通讯作者：
C. Monma;A. Schrijver;M. Todd;V. Wei
DOI：
10.1016/j.ejor.2004.12.008
发表时间：
2006-08
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
D. Shabtay;Moshe Kaspi
通讯作者：
D. Shabtay;Moshe Kaspi
影响因子：
1
作者：
Yaron Leyvand;D. Shabtay;G. Steiner;Liron Yedidsion
通讯作者：
Yaron Leyvand;D. Shabtay;G. Steiner;Liron Yedidsion
DOI：
10.1016/s0305-0548(03)00187-4
发表时间：
2004-11
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
D. Shabtay;Moshe Kaspi
通讯作者：
D. Shabtay;Moshe Kaspi