Constraint-based Techniques for Scheduling Discretionary Services

Abstract

A project network composed of discretionary tasks typically exists in service professions, such as journalism, clinic, software development or financial analysis, where the quality (or value) of a task increases with the time spent on it. Since a longer task duration consumes more resources (i.e., workers' time), the project manager must strike a balance between quality and time by scheduling tasks and setting their durations while respecting the project deadline, precedence and resource constraints. We formulate this problem, give a polynomial-time optimal algorithm for the single capacity case and prove the NP-completeness of the general multiple capacity case. Then we develop two hybrid solution procedures integrating linear optimization and an AI search procedure - precedence constraint posting - for the general case. Our results verify the effectiveness of these procedures and show there exists a potential synergy between objectives of maintaining temporal flexibility and maximizing quality, which implies that existing techniques in building flexible schedules can be adapted to solve this new class of problems.