A two-agent single-machine scheduling problem to minimize the total cost with release dates
详细信息 查看全文
- 作者：Du-Juan Wang ; Yunqiang Yin ; Wen-Hsiang Wu ; Wen-Hung Wu ; Chin-Chia Wu…
- 关键词：Scheduling ; Two ; agent ; Largest order value method ; Maximum weighted completion time
- 刊名：Soft Computing
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：21
- 期：3
- 页码：805-816
- 全文大小：
- 刊物类别：Engineering
- 刊物主题：Computational Intelligence; Artificial Intelligence (incl. Robotics); Mathematical Logic and Foundations; Control, Robotics, Mechatronics;
- 出版者：Springer Berlin Heidelberg
- ISSN：1433-7479
- 卷排序：21
文摘
This paper considers a two-agent scheduling problem with arbitrary release dates on a single machine. The cost of the first agent is the maximum weighted completion time of its jobs while the cost of the second agent is the total weighted completion time of its jobs. The goal is to schedule the jobs such that the total cost of the two agents is minimized. The problem is known to be strongly NP-hard. Thus, as an alternative, a branch-and-bound algorithm incorporating several dominance properties and a lower bound is provided to derive the optimal solution and a largest- order-value method combined with proposed three initials is developed to derive the near-optimal solutions for the problem. Computational results are also presented to evaluate the performance of the proposed algorithms.