Scheduling problems are often modeled as resource constrained problems in which critical resource assignments to tasks are known and the best assignment of resource time must be made subject to these constraints. Generalization to resource scheduling, where resource assignments are chosen concurrently with times results is a problem which is much more difficult. A simplified model of the general resource scheduling model is possible, however, in which tasks must be assigned a single primary resource, subject to constraints resulting from preassignment of secondary, or auxiliary, resources. This paper describes extensions and enhancements of tabu search for the special case of the resource scheduling problem described above. The class of problems is further restricted to those where it is reasonable to enumeate both feasible time and primary resource assignments. Potential applications include shift oriented production and manpower scheduling problems as well as course scheduling where classrooms (instructors) are primary and instructors (rooms) and students are secondary resources. The underlying model is a type of quadratic multiple choice problem which is called multiple choice quadratic vertex packing. Results for strategic oscillation and biased candidate sampling strategies are shown for reasonably sized real and randomly generated, synthetic, problem instances. The strategies are compared with other variations using consistent measures of solution time and quality developed for this study.
