Two-agent scheduling with generalized due dates

In this paper we consider the problems of order pickers in warehouse management. We interpret the problems as machine scheduling problems in which the due dates are not specified for the jobs but for their positions. In addition, we also consider the situation where there exist two types of orders: the primary (or urgent) order and the secondary (regular) order. These problems can be modeled as two-agent scheduling problems with generalized due dates. In particular we consider two environments: single-machine and the proportionate flow shop. Two objectives are considered: The first objective is to minimize one agent's performance measure with a constraint on the other agent's one, while the second objective is to minimize the weighted sum of the performance measures of two agents. The performance measures introduced in this paper are the maximum tardiness, the total tardiness, and the total number of tardy jobs. We show that under both machine environments, the case with the first objective is weakly NP-hard when the performance measures of two agents are the total tardiness, while the other cases are polynomially solvable.