Project scheduling under competition

We introduce and investigate the problem of scheduling activities of a project by a firm that competes with another firm (the competitor) that has to perform the same project. The profit that the firm gets from each activity depends on whether the firm finishes the activity before or after its competitor. The objective is to maximize the guaranteed (worst-case) profit. We assume that both the firm and the competitor can perform only one activity at a time. We perform a detailed complexity analysis of the problem, and consider problems with and without precedence constraints, with and without delay of the competitor, with general and equal processing times of activities. For polynomially solvable cases (which include, for example, all the considered problems without delay of the competitor), we present easily implementable and intuitive rules that allow us to obtain optimal schedules in linear or almost linear time. For some NP-hard cases, we present pseudopolynomial algorithms and fast heuristics with worst-case approximation guarantees. (c) 2005 Wiley Periodicals, Inc.