Machine Scheduling
Machine Scheduling
5. References
Assmann, S. and D. Johnson, D. Kleitman, J. Leung, On a dual version of the one-dimensional bin packing problem, J. Algorithms 5 (1984) 502-525.
Baker, B., A new proof for the first-fit decreasing bin-packing algorithm, J. Algorithms 6 (1985) 49-70.
Baker, B. and E. Coffman, Jr., A tight asymptotic bound for next-fit-decreasing bin packing, SIAM J. Alg. Disc. Math., 2 (1981) 147-152.
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. 51-58.
Bartal, Y. and H. Karloff, Y. Rabani, A better lower bound for on-line scheduling, Information Processing Letters, 50 (1994) 113-116.
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. 279-288.
Brucker, P., Scheduling Algorithms, Springer-Verlag, 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. 245-270.
Coffman, Jr., E. and C. Courcoubetis, M. Garey, D. Johnson, L. McGeoch, P. Shor, R. Weber, M. Yannakakis, Fundamental discrepancies between average-case analyses under discrete and continuous distributions: A bin packing case study, STOC, 19991, p. 230-240.
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) 227-258.
Coffman, Jr., E. and M. Garey, D. Johnson, Approximation Algorithms for Bin-Packing,: An updated survey, in Algorithm Design for Computer Systems Design, G. Ausiello, M. Lucertini, and P. Serafini, (eds.), Springer-Verlag, New York, 1984, 49-106.
Coffman, Jr., E. and M. Garey, D. Johnson, An application of bin-packing to multiprocessor scheduling, SIAM J. Comput., 7 (1987) 1-17.
Coffman, Jr., E. and M. Garey, D. Johnson, Approximation Algorithms for NP-Hard Problems, in D. Hochbaum, (ed.), Prindle Weber and Schmidt, Boston, 1996, p. 46-93.
Coffman, Jr., E. and M. Garey, D. Johnson, Bin Packing with divisible item sizes, J. Complexity, 3 (1987) 405-428.
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 ACM-SIAM 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) 105-115.
Conway, R. and W. Maxwell, L. Miller, Theory of Scheduling, Addison-Wesley, Reading, 1967.
Courcoubetis, C. and R. Weber, Necessary and sufficient conditions for the stability of a bin packing system, J. Appl. Prob., 23 (1986) 989-999.
Csirik, J., The parametric behavior of the first-fit decreasing bin packing algorithm, J. Algorithms 15 (1993) 1-28.
Csirik, J. and J. Frenk, G. Galambos, A. Rinnooy Kan, Probabilistic analysis of algorithms for dual bin packing problems, J. Algorithms 12 (1991) 189-203.
Csirik, J. and D. Johnson, Bounded space on-line bin packing; best is better than first, In Proceedings, Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1991, p. 309-319.
Fernandez del la Vega, W. and G. Lueker, Bin packing can be solved in 1 + e in linear time, Combinatorica 1 (1981) 34-355.
Flexzar, K. and K. Hindi, New heuristics for one-dimensional bin packing, Computers and Operations Research 29 (1902) 821-839.
Floyd, S. and R. Karp, FFD bin packing for items sizes with distribution on [0, 1/2], Algorithmica, 6 (1991) 222-240.
French, S., Sequencing and Scheduling, Wiley, New York, 1982.
Galambos, G. and G. Woeginger, An on-line scheduling heuristic with better worst case ratio than Graham's list scheduling, SIAM J. Computing, 22 (1993) 349-355.
Garey, M. and R. Graham, D. Johnson, A. Yao, Resource constrained scheduling as generalized bin packing, J. Combinatorial Theory Ser. A, 21 (1976) 257-298.
Garey, M., and D. Johnson, Approximation algorithms for bin packing problems-A survey, in Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini, (eds.)., Springer-Verlag, New York, 1981, p. 147-172.
Garey, M. and D. Johnson, A 71/60 theorem for bin packing, J. of Complexity, 1 (1985) 65-106.
Graham, R., Bounds for certain multiprocessing anomalies, Bell System Tech. J., 45 (1966) 1563-1581.
Graham, R., Bounds on multiprocessing anomalies, SIAM J. Applied Math., 17 (1969) 263-269.
Graham, R., Combinatorial Scheduling, in Mathematics Today, L. Steen, (Ed.), Springer-Verlag, New York, 1978, p. 183-211.
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) 287-326.
Gusfield, D., Bounds for naive multiple machine scheduling with release times and deadlines, J. of Algorithms, 5 (1984) 1-6.
Hoffman, The Man Who Loved Only Numbers, Hyperion, New York, 1998.
Hofri, M., Probabilistic Analysis of Algorithms, Springer-Verlag, New York, 1987.
Jackson, J., Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, UCLA, 1955.
Johnson, D., Near-Optimal Bin Packing Algorithms, Doctoral Thesis, MIT, Cambridge, 1973.
Johnson, D., Fast algorithms for bin packing, J. Comput. System Sci., 8 (1974) 272-314.
Johnson, D. and A Demers, J. Ullman, M. Garey, R. Graham, Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput., 3 (1974) 299-325.
Karger, D. and S. Phillips, E. Torng, A better algorithm for an ancient scheduling problem, In Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994, 132-140.
Karger, D. and C. Stein, J. Wein, Scheduling Algorithms, In Algorithms and Theory of Computation Handbook, M. Atallah, (ed.), CRC, Boca Raton, 1999, 35-1 - 35-33.
Karmarkar, N. and R. Karp, An efficient approximation scheme for the one-dimensional bin packing problem, Proc. 23rd Annual Symposium Foundation Computer Science (FOCS 1982), p. 312-320.
Katona, G., Edge disjoint polyp packing, Discrete Applied Mathematics 78 (1997) 133-152.
Kucera, L., Combinatorial Algorithms, Adam Hilger, Bristol, 1990.
Lawler, E., Optimal sequencing of a single machine subject to precedence constraints, Management Science, 19 (1973) 544-546.
Lenstra, J. and A. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977) 343-362.
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 n-job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968) 102-109.
Parker, R., Deterministic Scheduling, Chapman-Hall, 1995.
Pinedo, M., Scheduling: Theory, Algorithms, Systems, Prentice-Hall, Upper Saddle River, 1995.
Shor, P., The average case analysis of some on-line algorithms for bin packing, Combinatorica 6 (1986) 179-200.
Shor, P., How to pack better than best-fit: Tight bounds for average-case on-line bin packing. In Proceedings, 32 Annual Symp. on Foundations of Computer Science, New York, 1991, 752-759.
Simchi-Levi, D., New worst-case results for the bin packing problem, Naval Res. Log., 4 (1994( 579-585.
Smith, W., Various optimizers for single stage production, Naval Research Log. Quart., 3 (1956) 59-66.
Xu, K., A Bin-Packing 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) 207-227.
Yue, M. A simple proof of the inequality FFD(L) (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm, Acta. Math. Appl. Sinica 7 (1991) 321-331.
Yue, M., On the exact upper bound for the multifit processor scheduling algorithm, Ann. Oper. Res., 24 (1990) 233-260.
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
