Stochastic Scheduling to Minimize Expected Lateness in Multiple Identical Machines

Authors: Ghulam Zakria, Zailin Guan , Yasser Riaz Awan, Wan Lizhi

Abstract:

There are many real world problems in which parameters like the arrival time of new jobs, failure of resources, and completion time of jobs change continuously. This paper tackles the problem of scheduling jobs with random due dates on multiple identical machines in a stochastic environment. First to assign jobs to different machine centers LPT scheduling methods have been used, after that the particular sequence of jobs to be processed on the machine have been found using simple stochastic techniques. The performance parameter under consideration has been the maximum lateness concerning the stochastic due dates which are independent and exponentially distributed. At the end a relevant problem has been solved using the techniques in the paper..

Keywords: Quantity Production Flow Shop, LPT Scheduling, Stochastic Scheduling, Maximum Lateness, Random Due Dates

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331293

References:

[1] E. H. L. Aarts, M. J. Frans, and E. H. A. Habers, Parallel Implementations of the Statistical Cooling Algorithm, The VLSI Journal, Vol. 4, No. 3, pp. 209-238, 1986.
[2] T. Aoki, S. Nakayama, M. Yamamoto, M.Hashimoto, and J. Tanaka, Combinatorial scheduler: simulation & optimization algorithm, Proceedings of the 1991 Winter Simulation Conference. pp. 280-288, 1991.
[3] H. Cho and R. A. Wysk, A Robust Adaptive Scheduler for an intelligent Workstation Controller, International Journal of Production Research, Vol. 31, No. 4, pp. 771-789, 1993.
[4] W.J. Davis and A.T. Jones, Real-Time Simulation and Production Scheduling Systems, NIST report NISTIR 89-4070, 1989.
[5] F. Glover, Future Paths for Integer Programming and Links to Artificial Intelligence, Computers and Operations Research, Vol. 13, No. 5, pp. 533-549, 1986.
[6] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, England, 1989.
[7] A. J. Davenport, C. Gefflot, and J. C. Beck, Slack Based Techniques for Robust Schedules, Proceedings of the Sixth European Conference on Planning 7-18, 2001.
[8] D. W. Fowler and K. N. Brown, Branching Constraint Satisfaction Problems and Markov Decision Problems Compared, Annals of Operational research 118:85-100, 2003.
[9] R. L. Daniels and J. E. Carrillo, Beta-Robust Scheduling for Single Machine Systems with Uncertain Processing Times, IIE Transactions 29:977-985, 1997
[10] J. R. Jackson, Scheduling a Production like to Minimize Maximum Tardiness, Technical Report 43, University of California, Los Angeles, 1955.
[11] E. L. Lawler, Optimal Sequencing of a Single Machine Subject to Precedence Constraints, Management Science 19, pp. 544- 546, 1973.
[12] J. K. Lenstra, A. H. G. Rinnooy Kan and P. Brucker, Complexity of Machine Scheduling Problems, Annals of Operations Research 1, pp. 342-362, 1977.
[13] S. Chanas and A. Adam Kasperski, Minimizing Maximum Lateness on a Single Machine Scheduling Problem with Fuzzy Processing Times and Fuzzy Due Dates, Engineering Applications of Artificial Intelligence 14 , pp. 377-386, 2001.
[14] Tzung-Pei Hong, Pei-Ying Huang, and Gwoboa Horng, Using the LPT and the Palmer Approaches to Solve Group Flexible Flow-shop Problems, IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.3A, 2006.
[15] Xianyi Wu, Xian Zhou, Stochastic Scheduling to Minimize Expected Maximum Lateness, European Journal of Operational Research 190 103-115, 2008.