The Continuous Assignment Problem and Its Application to Preemptive and Non-Preemptive Scheduling with Irregular Cost Functions

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Upper Saddle River, NJ)Google Scholar
• Aurenhammer F. Power diagrams: properties, algorithms, and applications. SIAM J. Comput. (1987) 16:78–96Crossref, Google Scholar
• Aurenhammer F., Hoffmann F., Aronov B. Minkowski-type theorems and least-squares clustering. Algorithmica (1998) 20:61–76Crossref, Google Scholar
• Avram F., Bertsimas D., Ricard M., Kelly F., Williams R. Fluid models of sequencing problems in open queueing networks: An optimal control approach. Stochastic Networks The IMA Volumes in Mathematics and Its Applications. (1995) 71(Springer-Verlag, New York) 199–234Crossref, Google Scholar
• Bellman R. Bottleneck problem and dynamic programming. Proc. National Acad. Sci. USA (1953) 39:947–951Crossref, Google Scholar
• Bellman R.Dynamic Programming (1957) (Princeton University Press, Princeton, NJ) Google Scholar
• Bertsimas D., Gamarnik D. Asymptotically optimal algorithms for job shop scheduling and packet routing. J. Algorithms (1999) 33:296–318Crossref, Google Scholar
• Bertsimas D., Sethuraman J. From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective. Math. Programming, Ser. A (2002) 92:61–102Crossref, Google Scholar
• Boissonnat J. D., Yvinec M.Algorithmic Geometry (2001) (Cambridge University Press, Cambridge, U.K) Google Scholar
• Garey M. R., Tarjan R. E., Wilfong G. T. One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. (1988) 13:330–348Link, Google Scholar
• Grünbaum B.Convex Polytopes (1967) (Interscience, New York) Google Scholar
• Hoogeveen J. A., van de Velde S. L. A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. INFORMS J. Comput. (1996) 8:402–412Link, Google Scholar
• Khachian L. G. A polynomial algorithm in linear programming. Soviet Math. Doklady (1979) 20:191–194Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G., Brucker P. Complexity of machine scheduling problems. Ann. Discrete Math. (1977) 1:343–362Crossref, Google Scholar
• Luo X., Bertsimas D. A new algorithm for state-constrained separated continuous linear programs. SIAM J. Control Optim. (1998) 37:177–210Crossref, Google Scholar
• Marcus M., Ming H.A Survey of Matrix Theory and Matrix Inequalities (1964) (Allyn and Bacon, Inc., Boston, MA) Google Scholar
• Minoux M.Mathematical Programming: Theory and Algorithms (1986) (Wiley & Sons, New York) Google Scholar
• Philpott A. B., Craddock M. An adaptative discretization algorithm for a class of continuous network programs. Networks (1995) 26:1–11Crossref, Google Scholar
• Pullan M. C. A duality theory for separated continuous linear programs. SIAM J. Control Optim. (1996) 34:931–965Crossref, Google Scholar
• Schramm R. On piecewise linear functions and piecewise linear equations. Math. Oper. Res. (1980) 5:510–522Link, Google Scholar
• Shor N. Z. Convergence of a gradient method with space dilatation in the direction of the difference between two successive gradients. Kibernetika (1975) 11:48–53Google Scholar
• Shor N. Z. Cut-off methods with space extension in convex programming problems. Cybernetics (1977) 13:94–96Crossref, Google Scholar
• The one machine problem with earliness and tardiness penaltiesJ. Scheduling (2003) 6Google Scholar
• Vavasis S. A., Atallah M. J. Convex optimization. Algorithms and Theory of Computation Handbook (1998) (CRC Press, Boca Raton, FL) . Chap.33Crossref, Google Scholar
• Weiss G. A simplex based algorithm to solve separated continuous linear programs. Math. Programming. (2002) . ForthcomingGoogle Scholar