Bicriteria scheduling with vacations on a single machine

In many manufacturing systems, machines subject to vacations are found prevalently. In this paper we assume that a weekly working interval is 5 days and each vacation contains 2 days. There is a working interval between two vacations, in which jobs can be scheduled for processing. It is known that scheduling vacations in a planned schedule will result in several tardy jobs, and thereby a larger total flow time is generated. Therefore, our objective is to minimize the total flow time and the number of tardy jobs. A heuristic is developed to find a set of efficient schedules for the problem. We also present a branch-and-bound algorithm to find the optimal schedule. Computational results are provided to demonstrate the effectiveness of the heuristic.