Search

In this paper, we consider the two-agent scheduling problem with rejection on a single machine. In the problem we have two agents A and B with job families J A and J B , respectively. A job in J A or J B is either accepted and processed on the machine, or rejected with a certain rejection penalty having to be paid. The objective is to minimize the sum of the given objective function f A of the accepted jobs and total rejection penalty of the rejected jobs of the first agent A , given that the second agent B only accepts schedules such that the sum of the given objective function f B of the accepted jobs and total rejection penalty of the rejected jobs of the agent B does not exceed a fixed value Q ( Q is a positive integer), where f A and f B are non-decreasing functions on the completion times of their respective jobs. We show that, for all pairs ( f A , f B ) ∈ C max A , C max B , L max A , L max B , ∑ C j A , C max B , ∑ C j A , L max B , ∑ C j A , ∑ w j B U j B , the problems are NP-hard. When ( f A , f B ) = C max A , L max B , we provide a pseudo-polynomial-time algorithm. Moreover, when ( f A , f B ) = C max A , L max B and all B -jobs are accepted, we give a 2-approximation algorithm and an fully polynomial-time approximation scheme. Finally, for ( f A , f B ) ∈ ∑ C j A , L max B , ∑ C j A , ∑ w j B U j B K , we present pseudo-polynomial-time algorithms, respectively. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers bi-criteria scheduling on a single parallel-batch machine to minimizing two regular scheduling criteria that are non-decreasing in the job completion times. For minimizing the total weighted completion time and the makespan simultaneously, we prove that the problem is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. For minimizing the weighted total number of tardy jobs and the makespan simultaneously, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme. Furthermore, we identify that all Pareto-optimal solutions for and can be found in pseudo-polynomial time, respectively. [Copyright &y& Elsevier]