Assigning staff to engagements according to hard constraints while optimizing several objectives is a task encountered by many companies on a regular basis. Simplified versions of such assignment problems are NP-hard. Despite this, a typical approach to solving them consists of formulating them as mixed integer programming (MIP) problems and using a state-of-the-art solver to get solutions that closely approximate the optimum. In this paper, we consider a complex real-world staff assignment problem encountered by the professional service company KPMG, with the goal of finding an algorithm that solves it faster and with a better solution than a commercial MIP solver. We follow the evolutionary algorithm (EA) metaheuristic and design a search heuristic which iteratively improves a solution using domain-specific mutation operators. Furthermore, we use a flow algorithm to optimally solve a subproblem, which tremendously reduces the search space for the EA. For our real-world instance of the assignment problem, given the same total time budget of \(100\) hours, a parallel EA approach finds a solution that is only \(1.7\)% away from an upper bound for the (unknown) optimum within under five hours, while the MIP solver Gurobi still has a gap of \(10.5\) %.
Sutton, Andrew M.; Howe, Adele E.; Whitley, L. DarrellUsing Adaptive Priority Weighting to Direct Search in Probabilistic Scheduling. International Conference on Automated Planning and Scheduling (ICAPS) 2007: 320-327
Many scheduling problems reside in uncertain and dynamic environments - tasks have a nonzero probability of failure and may need to be rescheduled. In these cases, an optimized solution for a short-term time horizon may have a detrimental impact over a broader time scale. We examine a scheduling domain in which time and energy on a phased array radar system is allocated to track objects in orbit around the earth. This domain requires probabilistic modeling to optimize the expected number of successful tasks on a particular day. Failed tasks must be attempted again on subsequent days. Given a set of task requests, we study two long-term objectives: percentage of requests initially successful, and the average time between successful request updates. We investigate adaptive priority weighting strategies that directly influence the short-term objective function and thus indirectly influence the long-term goals. We find that adapting priority weights based on when individual tasks succeed or fail allows a catalog of requests to be filled more quickly. Furthermore, with adaptive priorities, we observe a Pareto-front effect between the two long-term objectives as we modify how priorities are weighted, but an inverse effect of weighting when the priorities are not adapted.
Sutton, Andrew M.; Howe, Adele E.; Whitley, L. DarrellSpacetrack: Trading off Quality and Utilization in Oversubscribed Schedules. International Conference on Automated Planning and Scheduling (ICAPS) 2006: 430-433
Many scheduling problems are posed as optimization problems where the goal is to find a feasible schedule that maximizes the utilization of some resource. In some domains it is also necessary to consider the quality of the resulting schedule. In most research these two quantities are independent. This paper introduces a real world problem in which radar tasks must be allocated to track objects in space. We explore the trade-off between off-line task resource utilization and a measure of task quality that correlates to whether tasks are actually successfully executed. We develop two general types of algorithms that differ in the way they reason about quality and explore the trade-off between high quality solutions and solutions with high resource utilization.
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.