Some two-agent single-machine scheduling problems to minimize minmax and minsum of completion times

In this study we address several two-agent problems in which the measure criterion is to minimize the maximum cost or total weighted completion of all the jobs, while subject to an upper bound on the maximum cost of agent A. In term of minimizing the maximum cost of all the jobs subject to an upper bound on the maximum cost of agent A, we discuss some optimal properties and propose polynomial time solution algorithm to solve it. In term of minimizing the total weighted completion of all the jobs subject to an upper bound on the maximum cost of agent A, we analyze the complexity, show that this problem is NP-hard, and discuss it under special cases. In addition, for minimizing the total weighted completion of all the jobs subject to an upper bound on the makespan of agent A, we derive some dominance rules to be used in a branch-and-bound method and propose a heuristic for finding the optimal and near-optimal solution, respectively. A computational simulation is also provided to determine the performance of the proposed algorithms.