A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system
A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system
复制标题
DOI：
10.1016/j.ijpe.2011.09.011
复制
发表时间：
2012-03
影响因子：
12
通讯作者：
D. Shabtay;Yaron Bensoussan;Moshe Kaspi
中科院分区：
文献类型：
--
作者：
D. Shabtay;Yaron Bensoussan;Moshe Kaspi
我们分析了两台机器的流水车间调度问题，其中的作业处理时间是可控的资源分配的作业操作和资源可以在离散量使用。我们提供了一个双准则分析的问题，第一个标准是最大限度地提高加权数量的即时工作和第二个标准是最小化的总资源消耗成本。我们证明，虽然这个问题是已知的NP-难，即使是恒定的处理时间，其解决方案存在一个伪多项式时间算法。此外，我们展示了如何伪多项式时间算法可以转换成一个二维的完全多项式近似计划找到一个近似的Pareto解决方案。
We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.