Bounded scheduling two-component jobs simultaneously or hierarchically

School of Computer Science, University of St Andrews, St Andrews KY16 9SX, UK

^* Corresponding author: yjliyt@hotmail.com

Abstract

This paper studies the multi-objective problem of scheduling n two-component jobs on a fabrication machine with bounded batch capacity in terms of the number of jobs. Each job consists of two components, one is common among all jobs (called standard component) and the other is unique to itself (called specific component). The machine processes all components so that it might become a capacitated bottleneck machine. Standard components have equal processing times. They are fabricated in batches sequentially on the machine, and a setup time is required to fabricate a batch. Each batch contains the standard components of at most b(b < n) jobs. Specific components are manufactured individually, therefore their associated setup times could be absorbed into their processing times. Standard components in a batch are not available until all these components are completed (meaning that the processing time of a batch is equal to the total processing time of the standard components in it), whereas a specific component is available on completion of its processing. A job is completed when both its two components are completed and available. For simultaneous optimization of makespan and maximum lateness, an O(n³)-time algorithm is obtained. Through a careful use of the heap data structure, the time bound can be improved to O(n² log n). For hierarchical optimization of two maximum lateness objectives and makespan, an O(n⁵)-time algorithm is obtained, which can be improved to run in time O(n⁴).