Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
复制标题
DOI：
10.1287/ijoc.2015.0660
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
中科院分区：
文献类型：
--
作者：
A. Shioura;N. V. Shakhlevich;V. Strusevich
本文研究了一个单机上的作业调度问题，在此条件下，作业具有独立的发布日期和截止日期，并且加工时间是可控的。目标是找到一个可行的时间表，使减少处理时间的总成本最小化。我们将问题重新表述为在与盒子相交的次模多面体上最大化线性函数。对于后一个子模块优化问题，我们开发了一种递归分解算法，并将其应用于解决单机调度问题，以实现最佳运行时间。
In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time.