Determining job completion time distributions in stochastic production environments

ABSTRACT

As responsiveness becomes more of a competitive issue, knowledge of completion times of jobs and orders on the shop floor is key to the success and even survival of many manufacturing firms. We present two approaches-a fast sample path generation technique and a numerical technique-to determine the distribution of completion times of jobs in stochastic production environments. We compare our results with those obtained from conventional discrete event simulation and also compare speed of execution. We also show that the distribution obtained from the numerical integration technique provides a lower bound to the actual distribution of the completion times.

References

1. Baker, K. R., 1984. Sequencing Rules and Due-date Assignments in a Job Shop, Management Science, 30(9): 1093-2004.
2. Bertrand, j. W. M., 1983. Effect of Workload Dependent Due-dates on Job Shop Performance, Management Science, 29(7): 799-816.
3. Bickel, P. J., K. A. Doksum, 1977. Mathematzcal Statistics: Basic Ideas and Selected Topzcs, Holden-Day Inc. CA.
4. Bookbinder, J. H., A. I. Noor, 1985. Setting Job-shop Due-dates with Service-level Constraints, Journal of Operational Research Society, 36: 1017-1026.
5. Buzzacott, J. A., J. G. Shanthikumar, 1985. Approximate Queuing Models of Dynamic Job Shops, Management Science, 31(7): 870-887.
6. Cheng, T. C. E., 1985. Analysis of Flow-time in a Job Shop, Journal of Operational Research Society, 36: 225-239.
7. Eilon, S., I. G. Chowdhury, 1976. Due-dates in Job Shop Scheduling, International Journal of Production Research, Vol. 14.
8. Fisz, M., 1963. Probability Theory and Mathematical Statistics, 3rd edition, John Wiley & Sons, Inc., New York.
9. Fleming P. J., B. Simon, 1991. Interpolation Approximation of Sojourn Time Distributions, Operations Research, 39(2): 251-260.
10. Fry, T. D., P. R. Philipoom, R. E. Markland, 1989. Due-date Assignment in a Multi-stage Job Shop", IIE Transactions, 21(2).
11. Hasan, C. N., 1991. MACSim 1.0: User's and Programmer's Manual, Unpublished Master's thesis, McCormick School of Engineering and Applied Sciences, Northwestern University, Evanston, Illinois.
12. Jackson, J. R., 1963. Job-shop Like Queueing Systems, Management Science, 10(1): 131-142.
13. Karmarkar, U. S., 1993. Manufacturing Lead Times, Order Release and Capacity Loading, In Handbooks in OR ~d MS, Vol. 4, 287-329, S. C. Graves el al., eds., North-Holland, Amsterdam.
14. Kleinrock, L., 1975. Queueing Systems, Volume I: Theory, John Wiley & Sons, New York.
15. Kotiah, T. C. T., 1978. Approximate Transient Analysis of Some Queuing Systems, Operat,ons Research, 26(2).
16. Kou|amas C. P., 1992. Exact Expressions for the First Two Moments of Job Flow Time in a Job Shop, Journal of Operational Research Society, 43(9).
17. Miyazaki, S., 1981. Combined Scheduling System for Reducing Job Tardiness in a Job Shop, Internatzonal Journal of Productzon Research, Vol. 19.
18. Mori, M., 1976. Transient Behavior of the Mean Waiting Time and Its Exact Forms in M/M/1 and M/D/1 Queues, Journal of Operatzonal Research Society, Japan, 19(1).
19. Pack, C. D., 1978. The Output of a Multiserver Queueing System, Operations Research, 26(3): 492-509.
20. Ross, S. M., 1983. Stochastic Processes, John Wiley & Sons, New York.
21. Rubinstein, R. Y., 1986. Monte Carlo Optimization, Simulation and Sensitivity of Queueing Networks, John Wiley & Sons, New York.
22. Saboo, S., L. Wang, W. E. Wilhelm, 1989. Recursion Models For Describing and Managing the Transient Flow of Materials in Generalized Flowlines, Managemenl Sczence, 35(6): 722-742.
23. Schmeiser, B., W. T. Song, 1989. inversetransformation Algorithms for Some Common Stochastic Processes, Proceedings of the 1989 Winter Simulation Conference, E. A. MacNair, K. J. Musselman, P. Heidelberger, eds.
24. Seidmann, A., M. L. Smith, 1981. Due-date Assignment for Production Systems, Management Science, 27(5): 571-580.
25. Shanthikumar, J. G., U. Sumita, 1988. Time Spent in a Dynamic Job Shop, International Journal of Productzon Research, 26(8): 1329-1352.
26. Spearman, M. L., R. Q. Zhang, 1994. Optimal Lead Times in Manufacturing Systems, working paper, Department of Industrial Engineering and Management Sciences, Northwestern University.
27. Sumita, U., 1981. Development of the Laguerre Transform Method for Numerical Exploration of Applied Probability Models, Unpublished Ph.D. Thesis, Graduate School of Management, University of Rochester, Rochester, New York.
28. Taylor III, B. W., L. J. Moore, 1982. Estimating Job Flow-times in a Job Shop for Contractually Negotiated Due-dates, Journal of Operational Research Society, Vol. 33.
29. Weeks, J. A., 1979. A Simulation Study of Predictable Due-dates, Management Science, 25(4): 363-373.
30. Weeks, J. K., J. S. Fryer, 1977. Methodology for Assigning Minimum cost Due-dates, Management Science, 23(8): 1362-1371.
31. Wein, L. M., 1991. Due-date Setting and Priority Sequencing in a Multi-class M/G/1 Queue, Management Sczence, 37(7): 1018-1033.
32. Wein, L. M., P. B. Chevalier, 1992. A Broader View of the Job-shop Scheduling Problem, Management Sczence, 38(7).
33. Whitt, W., 1983. The Queueing Network Analyzer, Bell Systems Technzcal Journal, 62(9): 2779-2815.

Index Terms

• Applied computing

  • Computers in other domains

• Computer systems organization

  • Real-time systems

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Software and its engineering

  • Software creation and management

    • Designing software

      • Software implementation planning

        • Software design techniques

    • Software development process management

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

        • Stochastic control and optimization