A survey of due-date related single-machine with two-agent scheduling problem

In this paper, we consider due-date related single machine scheduling problems, where two agents compete for utilizing a common processing resource (i.e. a single machine). In this paper, we provide a detailed and a systemic literature review of the two-agent scheduling problem dealing with models with a given due date. We consider the following four main cases: 1) the earliness and tardiness, 2) the maximum lateness, 3) the number of tardy jobs and 4) the late work criteria. To do so, we 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 their weighted objectives. In the present paper, we list the computational complexities and proposed algorithms for the due-date related, two-agent scheduling problem, investigated in the literature since 2003.