×

On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups. (English) Zbl 1185.90087

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baptiste, P.; Brucker, P.; Knust, S.; Timkovsky, V., Ten notes on equal-processing-time scheduling, 4OR Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2, 111-127 (2004) · Zbl 1070.90041
[2] P. Baptiste, C. Le Pape, Scheduling a single machine to minimize a regular objective function under setup constraints, Discrete Optimization 2, 83-99; P. Baptiste, C. Le Pape, Scheduling a single machine to minimize a regular objective function under setup constraints, Discrete Optimization 2, 83-99 · Zbl 1140.90390
[3] Bartal, Y.; Leonardi, S.; Marchetti-Spaccamela, A.; Squal, J.; Stougie, L., Multiprocessor scheduling with rejection, SIAM Journal on Discrete Mathematics, 13, 1, 64-78 (2003) · Zbl 0936.68012
[4] Benoist, T.; Bourreau, E.; Caseau, Y.; Rottembourg, B., Towards stochastic constraint programming: A study of on-line multi-choice knapsack with deadlines, (Proceedings CP’01. Proceedings CP’01, LNCS, vol. 2239 (2001), Springer), 61-76 · Zbl 1067.68615
[5] Engels, D. W.; Karger, D. R.; Kolliopoulos, S. G.; Sengupta, S.; Uma, R. N.; Wein, J., Techniques for scheduling with rejection, Journal of Algorithms, 49, 175-191 (2003) · Zbl 1067.68024
[6] Finke, G.; Jost, V.; Queyranne, M.; Sebö, A., Batch processing with interval graphs compatibilities between tasks, Discrete Applied Mathematics, 156, 5, 556-568 (2008) · Zbl 1172.90399
[7] Gardi, F., Mutual exclusion scheduling with interval graphs or related classes, Discrete Applied Mathematics, 157, 1, 19-35 (2008) · Zbl 1155.90381
[8] György, D.; Yong, H., Scheduling with machine cost and rejection, Journal of Combinatorial Optimization, 12, 4, 337-350 (2006) · Zbl 1126.90021
[9] Hoogeven, H.; Skutella, M.; Woeginger, G. J., Preemptive scheduling with rejection, Mathematical Programming, 94, 2-3, 361-374 (2003) · Zbl 1030.90025
[10] Seiden, S., Preemptive multiprocessor with rejection, Theoretical Computer Science, 262, 1, 437-458 (2001) · Zbl 0992.68072
[11] van den Akker, M.; Hoogeveen, H., Minimizing the number of tardy jobs, (Leung, J. Y-T., Handbook of Scheduling (2004)), (Chapter 12) · Zbl 1168.90484
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.