Stochastic Scheduling to Minimize Expected Lateness in Multiple Identical Machines
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..
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:53082", author = "Ghulam Zakria and Zailin Guan and Yasser Riaz Awan and Wan Lizhi", title = "Stochastic Scheduling to Minimize Expected Lateness in Multiple Identical Machines", 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", volume = "4", number = "1", pages = "1-5", }
