Minimal Resources for Fixed and Variable Job Schedules

We treat the following problem: There are n jobs with given processing times and an interval for each job's starting time. Each job must be processed, without interruption, on any one of an unlimited set of identical machines. A machine may process any job, but no more than one job at any point in time. We want to find the starting time of each job such that the number of machines required to process all jobs is minimal. In addition, the assignment of jobs to each machine must be found. If every job has a fixed starting time (the interval is a point), the problem is well-known as a special case of Dilworth's problem. We term it the fixed job schedule problem (FSP). When the job starting times are variable, the problem is referred to as the variable job schedule problem (VSP), for which no known exact solution procedure exists. We introduce the problems by reviewing previous solution methods to Dilworth's problem. We offer an approximate solution procedure for solving VSP based on the entropy principle of informational smoothing. We then formulate VSP as a pure integer programming problem and provide an exact algorithm. This algorithm examines a sequence of feasibility capacitated transportation problems with job splitting elimination side constraints. Our computational experience demonstrates the utility of the entropy approach.