Two-agent scheduling in a flowshop
Two-agent scheduling in a flowshop
复制标题
DOI：
10.1016/j.ejor.2016.01.009
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
B. Q. Fan;B. Q. Fan;T. Cheng
中科院分区：
文献类型：
--
作者：
B. Q. Fan;B. Q. Fan;T. Cheng
在本文中，我们研究了两机流程中的双代理调度。成本函数是一些常见常规函数的加权和，包括完工时间和总完成时间。具体来说，我们考虑两个问题，即最小化两个智能体的完工时间的加权和的问题，以及最小化一个智能体的总完成时间和另一个智能体的完工时间的加权和的问题。对于第一个问题，我们给出了一个普通的 NP 难度证明和一个伪多项式时间算法。我们还分析了使用约翰逊规则处理问题的性能，并提出了一种基于约翰逊规则的近似算法。对于第二个问题，我们提出了一种基于问题的线性规划松弛的近似算法。最后，我们展示了一些简单的算法可以用来解决这两个问题的特殊情况。
In this paper we study two-agent scheduling in a two-machine flowshop. The cost function is the weighted sum of some common regular functions, including the makespan and the total completion time. Specifically, we consider two problems, namely the problem to minimize the weighted sum of both agents’ makespan, and the problem to minimize the weighted sum of one agent’s total completion time and the other agent’s makespan. For the first problem, we give an ordinary NP-hardness proof and a pseudo-polynomial-time algorithm. We also analyze the performance of treating the problem using Johnson’s rule and propose an approximation algorithm based on Johnson’s rule. For the second problem, we propose an approximation algorithm based on linear programming relaxation of the problem. Finally, we show that some simple algorithms can be used to solve special cases of the two problems.