On maximizing the profit of a satellite launcher: Selecting and scheduling tasks with time windows and setups

At regular times, a satellite launcher company has to plan the use of its launcher to get the maximum profit. In a more formal way, the problem consists of selecting and scheduling a subset of unit-length jobs constrained by capacitated time slots so that the overall cost is a minimum. The data associated with each job are its weight, its time-window and its expected gain when it is performed. With each time slot are associated a setup cost and a capacity. The setup cost of a time slot is due when this time-slot is used to perform at least one job. Moreover the total weight of all jobs scheduled within a time slot is at most the time slot capacity. We first show that the general problem is hard and provide some easy special cases. We then propose a first dynamic-programming polynomial-time algorithm for the special case with unit weights. A second and more efficient dynamic programming algorithm is also provided for the special case of unit weights and agreeable time windows. This last algorithm is finally improved for the special case of equal gains.