Experimental Design in the Scheduling of Two Unrelated Parallel Processors

Given a group of tasks and two non-identical processors with the ability to complete each task, which tasks should be assigned to which processor to complete the group of tasks in as short amount of time as possible? Processors may be airport runways, shipping trucks, manufacturing lines, computer processors, or surgeons. The tasks may be airplane take-offs and landings, packages to be shipped, products to be built, computer codes to be run, or patients to be operated on. This problem has been formalized in the scheduling literature as the minimization of the makespan (time required to complete all tasks) for two unrelated parallel processors.

One possible approach to solving this problem is to simulate the process, consider the computed processing times for all possible assignment schedules (complete enumeration), and select the assignment schedule that produces the minimum makespan. A typical implementation of the complete enumeration approach is to calculate the makespan for each assignment schedule one by one, noting the minimum makespan and associated assignment schedule observed thus far. This talk discusses the benefit realized by implementing the complete enumeration approach using a 2k full factorial experimental design framework, as illustrated by a printed circuit board assembly case study. Also explored is the possibility of employing the 2k - p fractional factorial experimental design structure in the solution of the two unrelated parallel processors problem.

Dennis Leber
Statistical Engineering Division/ITL