Machine Scheduling
Machine Scheduling
5. References
Assmann, S. and D. Johnson, D. Kleitman, J. Leung, On a dual version of the onedimensional bin packing problem, J. Algorithms 5 (1984) 502525.
Baker, B., A new proof for the firstfit decreasing binpacking algorithm, J. Algorithms 6 (1985) 4970.
Baker, B. and E. Coffman, Jr., A tight asymptotic bound for nextfitdecreasing bin packing, SIAM J. Alg. Disc. Math., 2 (1981) 147152.
Baker, K., Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
Bartal, Y. and A. Fiat, H. Karloff, R. Vohra, New algorithms for an ancient scheduling problem, In Proc. 24th ACM Symposium on the Theory of Computing, 1992, p. 5158.
Bartal, Y. and H. Karloff, Y. Rabani, A better lower bound for online scheduling, Information Processing Letters, 50 (1994) 113116.
Bentley, J. and D. Johnson, F. Leighton, C. McGeoch, L. McGeoch, Some unexpected expected behavior results for bin packing., in Proceedings of the 16th Annual ACM Sym. on Theory of Computing, 1984, p. 279288.
Brucker, P., Scheduling Algorithms, SpringerVerlag, New York, 1995.
Coffman, Jr., E., (Ed.), Computer & Job/Shop Scheduling Theory, Wiley, New York, 1976.
Coffman, Jr., E. An introduction to proof techniques for packing and sequencing algorithms, in Deterministic and Stochastic Scheduling, M. Dempster, et al., (eds.), Reidel, Amsterdam, 1982, p. 245270.
Coffman, Jr., E. and C. Courcoubetis, M. Garey, D. Johnson, L. McGeoch, P. Shor, R. Weber, M. Yannakakis, Fundamental discrepancies between averagecase analyses under discrete and continuous distributions: A bin packing case study, STOC, 19991, p. 230240.
Coffman, Jr., E. and G. Galambos, S. Martello, and D. Vigo, Bin Packing Approximation Algorithms: Combinatorial Analysis, in Handbook of Combinatorial Optimization, D. Du and P. Pardalos, (eds.), Kluwer, Amsterdam, 1998.
Coffman, Jr., E. and M. Garey, D. Johnson, Dynamic bin packing, SIAM J. Comput., 12 (1983) 227258.
Coffman, Jr., E. and M. Garey, D. Johnson, Approximation Algorithms for BinPacking,: An updated survey, in Algorithm Design for Computer Systems Design, G. Ausiello, M. Lucertini, and P. Serafini, (eds.), SpringerVerlag, New York, 1984, 49106.
Coffman, Jr., E. and M. Garey, D. Johnson, An application of binpacking to multiprocessor scheduling, SIAM J. Comput., 7 (1987) 117.
Coffman, Jr., E. and M. Garey, D. Johnson, Approximation Algorithms for NPHard Problems, in D. Hochbaum, (ed.), Prindle Weber and Schmidt, Boston, 1996, p. 4693.
Coffman, Jr., E. and M. Garey, D. Johnson, Bin Packing with divisible item sizes, J. Complexity, 3 (1987) 405428.
Coffman, Jr., E. and G. Lueker, Probabilistic Analysis of Packing and Partition Algorithms, Wiley, New York, 1991.
Coffman, Jr., E. and G. Lueker, Approximation Algorithms for extensible bin packing, Proceedings, 12th Annual ACMSIAM Symposium on Discrete Algorithms, 2001.
Coffman, Jr., E. and K. So, M. Hofri, A. Yao, A stochastic model of bin packing, Information and Control 44 (1980) 105115.
Conway, R. and W. Maxwell, L. Miller, Theory of Scheduling, AddisonWesley, Reading, 1967.
Courcoubetis, C. and R. Weber, Necessary and sufficient conditions for the stability of a bin packing system, J. Appl. Prob., 23 (1986) 989999.
Csirik, J., The parametric behavior of the firstfit decreasing bin packing algorithm, J. Algorithms 15 (1993) 128.
Csirik, J. and J. Frenk, G. Galambos, A. Rinnooy Kan, Probabilistic analysis of algorithms for dual bin packing problems, J. Algorithms 12 (1991) 189203.
Csirik, J. and D. Johnson, Bounded space online bin packing; best is better than first, In Proceedings, Second Annual ACMSIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, p. 309319.
Fernandez del la Vega, W. and G. Lueker, Bin packing can be solved in 1 + e in linear time, Combinatorica 1 (1981) 34355.
Flexzar, K. and K. Hindi, New heuristics for onedimensional bin packing, Computers and Operations Research 29 (1902) 821839.
Floyd, S. and R. Karp, FFD bin packing for items sizes with distribution on [0, 1/2], Algorithmica, 6 (1991) 222240.
French, S., Sequencing and Scheduling, Wiley, New York, 1982.
Galambos, G. and G. Woeginger, An online scheduling heuristic with better worst case ratio than Graham's list scheduling, SIAM J. Computing, 22 (1993) 349355.
Garey, M. and R. Graham, D. Johnson, A. Yao, Resource constrained scheduling as generalized bin packing, J. Combinatorial Theory Ser. A, 21 (1976) 257298.
Garey, M., and D. Johnson, Approximation algorithms for bin packing problemsA survey, in Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini, (eds.)., SpringerVerlag, New York, 1981, p. 147172.
Garey, M. and D. Johnson, A 71/60 theorem for bin packing, J. of Complexity, 1 (1985) 65106.
Graham, R., Bounds for certain multiprocessing anomalies, Bell System Tech. J., 45 (1966) 15631581.
Graham, R., Bounds on multiprocessing anomalies, SIAM J. Applied Math., 17 (1969) 263269.
Graham, R., Combinatorial Scheduling, in Mathematics Today, L. Steen, (Ed.), SpringerVerlag, New York, 1978, p. 183211.
Graham, R., and E. Lawler, E. Lenstra, A. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979) 287326.
Gusfield, D., Bounds for naive multiple machine scheduling with release times and deadlines, J. of Algorithms, 5 (1984) 16.
Hoffman, The Man Who Loved Only Numbers, Hyperion, New York, 1998.
Hofri, M., Probabilistic Analysis of Algorithms, SpringerVerlag, New York, 1987.
Jackson, J., Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, UCLA, 1955.
Johnson, D., NearOptimal Bin Packing Algorithms, Doctoral Thesis, MIT, Cambridge, 1973.
Johnson, D., Fast algorithms for bin packing, J. Comput. System Sci., 8 (1974) 272314.
Johnson, D. and A Demers, J. Ullman, M. Garey, R. Graham, Worstcase performance bounds for simple onedimensional packing algorithms, SIAM J. Comput., 3 (1974) 299325.
Karger, D. and S. Phillips, E. Torng, A better algorithm for an ancient scheduling problem, In Proc. 5th ACMSIAM Symposium on Discrete Algorithms, 1994, 132140.
Karger, D. and C. Stein, J. Wein, Scheduling Algorithms, In Algorithms and Theory of Computation Handbook, M. Atallah, (ed.), CRC, Boca Raton, 1999, 351  3533.
Karmarkar, N. and R. Karp, An efficient approximation scheme for the onedimensional bin packing problem, Proc. 23rd Annual Symposium Foundation Computer Science (FOCS 1982), p. 312320.
Katona, G., Edge disjoint polyp packing, Discrete Applied Mathematics 78 (1997) 133152.
Kucera, L., Combinatorial Algorithms, Adam Hilger, Bristol, 1990.
Lawler, E., Optimal sequencing of a single machine subject to precedence constraints, Management Science, 19 (1973) 544546.
Lenstra, J. and A. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977) 343362.
Leung, J., (ed.), Handbook of Scheduling, Chapman and Hall/CRC, Boca Raton, 2003.
Malkevitch, J. et al., For All Practical Purposes, (6th, and earlier editions) W. H. Freeman, New York, 2003.
Moore, J., An njob, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968) 102109.
Parker, R., Deterministic Scheduling, ChapmanHall, 1995.
Pinedo, M., Scheduling: Theory, Algorithms, Systems, PrenticeHall, Upper Saddle River, 1995.
Shor, P., The average case analysis of some online algorithms for bin packing, Combinatorica 6 (1986) 179200.
Shor, P., How to pack better than bestfit: Tight bounds for averagecase online bin packing. In Proceedings, 32 Annual Symp. on Foundations of Computer Science, New York, 1991, 752759.
SimchiLevi, D., New worstcase results for the bin packing problem, Naval Res. Log., 4 (1994( 579585.
Smith, W., Various optimizers for single stage production, Naval Research Log. Quart., 3 (1956) 5966.
Xu, K., A BinPacking Problem with Item Sizes in the Interval (o, a] for a 1/2, Doctoral Thesis, Chinese Academy of Sciences, Beijing, China, 1993.
Yao, A., New algorithms for bin packing. J. Assoc. Comput. Mach., 22 (1980) 207227.
Yue, M. A simple proof of the inequality FFD(L) (11/9)OPT(L) + 1, for all L, for the FFD binpacking algorithm, Acta. Math. Appl. Sinica 7 (1991) 321331.
Yue, M., On the exact upper bound for the multifit processor scheduling algorithm, Ann. Oper. Res., 24 (1990) 233260.
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal, which also provides bibliographic services.
 Introduction
 Modeling scheduling
 Paradoxical behavior
 Performance measures
 References

Welcome to the
Feature Column!
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .
Feature Column at a glance
