부산대학교 도서관

In this paper, the authors consider due-date related single-machinescheduling problems, where two agents compete for utilizing a commonprocessing resource (i.e., a single machine). They provide a detailed,systematic review of the literature on two-agent scheduling problemsdealing with models with a given due date. They study four differentcases of objective functions focusing on (1) the earliness andtardiness, (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 theobjective function setting (i.e., the feasibility model and theminimality model). The feasibility model minimizes the objectivefunction of one agent subject to an upper bound on the objective forthe other agent. The minimality model assigns certain weights for twoagents and as a result minimizes the sum of their weighted objectives.In this paper, the authors list the computational complexities andpropose algorithms for the due-date related, two-agent schedulingproblem, investigated in the literature since 2003.