부산대학교 도서관

In this paper, the authors consider due-date related single-machine scheduling problems, where two agents compete for utilizing a common processing resource (i.e., a single machine). They provide a detailed, systematic review of the literature on two-agent scheduling problems dealing with models with a given due date. They study four different cases of objective functions focusing on (1) the earliness and tardiness, (2) the maximum lateness, (3) the number of tardy jobs, and (4) the late work. Furthermore, they also classify due-date related, two-agent scheduling problems into two categories on the basis of the objective function setting (i.e., the feasibility model and the minimality model). The feasibility model minimizes the objective function of one agent subject to an upper bound on the objective for the other agent. The minimality model assigns certain weights for two agents and as a result minimizes the sum of their weighted objectives. In this paper, the authors list the computational complexities and propose algorithms for the due-date related, two-agent scheduling problem, investigated in the literature since 2003.