Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959845 | European Journal of Operational Research | 2017 | 20 Pages |
Abstract
We consider a two-agent scheduling problem on parallel machines such that each task of agent 2 has a given time window. Furthermore, we introduce a resource constraint under which the number of simultaneously processed tasks of agent 2 is restricted, although some machines are available. The objective is to minimize the total completion time for agent 1 while the total weight of the processed tasks for agent 2 is at or above a given threshold. Because the problem is known to be strongly NP-hard, we focus on the case with unit processing time. We analyze the computational complexity for its special cases, which have some restrictions on four parameters: the weight and the duration of agent 2, the number of machines, and the maximum number of simultaneously processed tasks of agent 2.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Byung-Cheon Choi, Myoung-Ju Park,