Abstract
We study a range of counterparts of the single-machine scheduling problem with the maximum lateness criterion that arise in the context of inverse optimization. While in the forward scheduling problem all parameters are given and the objective is to find the optimal job sequence for which the value of the maximum lateness is minimum, in inverse scheduling the exact values of processing times or due dates are unknown, and they should be determined so that a prespecified solution becomes optimal. We perform a fairly complete classification of the corresponding inverse models under different types of norms that measure the deviation of adjusted parameters from their given estimates.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Ahuja, R. K., & Orlin, J. B. (2001). Inverse optimization. Operations Research, 49, 771–783.
Brucker, P. (2004). Scheduling algorithms. Berlin: Springer.
Choi, K., Jung, G., Kim, T., & Jung, S. (1998). Real-time scheduling algorithm for minimizing maximum weighted error with O(Nlog N+cN) complexity. Information Processing Letters, 67, 311–315.
Duin, C. W., & Volgenant, A. (2006). Some inverse optimization problem under the Hamming distance. European Journal of Operational Research, 170, 887–899.
Heuberger, C. (2004). Inverse combinatorial optimization: a survey on problems, methods and results. Journal of Combinatorial Optimization, 8, 329–361.
Hochbaum, D. S., & Hong, S.-P. (1995). About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Mathematical Programming, 69, 269–309.
Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness (Research Report 43). Management Science Research Project, University of California, Los Angeles, USA.
Katoh, N., & Ibaraki, T. (1998). Resource allocation problems. In D.-Z. Du & P. M. Pardalos (Eds.) Handbook of combinatorial optimization (Vol. 2, pp. 159–260). Norwell: Kluwer Academic.
Lin, Y., & Wang, X. (2007). Necessary and sufficient conditions of optimality for some classical scheduling problems. European Journal of Operational Research, 176, 809–818.
Liu, L., & Zhang, J. (2006). Inverse maximum flow problems under the weighted Hamming distance. Journal of Combinatorial Optimization, 12, 395–408.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Brucker, P., Shakhlevich, N.V. Inverse scheduling with maximum lateness objective. J Sched 12, 475–488 (2009). https://doi.org/10.1007/s10951-009-0117-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-009-0117-9