Abstract
In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bilò V, Flammini M, Moscardelli L (2006) Pareto approximations for the bicriteria scheduling problem. J Parallel Distrib Comput 66:393–402
He C, Lin YX, Yuan JJ (2007) Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theor Comput Sci 381:234–240
Hoogeveen H (2005) Multicriteria scheduling. Eur J Oper Res 167:592–623
Hoogeveen JA (1996) Minimizing maximum promptness and maximum lateness on a single machine. Math Oper Res 21:100–114
Hoogeveen JA (1996) Single-machine scheduling to minimize a function of two or three maximum cost criteria. J Algorithms 21:415–433
Hoogeveen JA, Vestjens APA (2000) A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. SIAM J Discret Math 13:56–63
Ma R, Yuan JJ (2014) Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time. Int J Prod Econ 158:114–119
Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28:1436–1441
Pruhs K, Sgall J, Torng E (2004) Online scheduling. In: Leung JY-T (ed) Handbook of scheduling: algorithm, models, and performance analysis. Chapman and Hall/CRC, Boca Raton
Stein C, Wein J (1997) On the existence of schedules that are near-optimal for both makespan and total weighted completion time. Oper Res Lett 21:115–122
Acknowledgments
The authors would like to thank the associate editor and two anonymous referees for their constructive comments and kind suggestions. Foundation item: Supported by NSFC (11271338), NSFC (11171313), and NSFC (11301528).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, Q., Yuan, J. Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness. J Comb Optim 32, 385–395 (2016). https://doi.org/10.1007/s10878-015-9918-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9918-2