A Similarity Measure of Schedules and Robustness Evaluation of Priority Rules

Abstract:

The present paper attempts to clarify which priority rule is appropriate for specific manufacturing environment variations, such as processing time variations, operation additions, and additional job releases. In such manufacturing environments, the performance of scheduling rules should be evaluated with a degree of robustness under dynamic situations and traditional measures, such as makespan, under static situations. The present paper evaluates the robustness of the priority rules FCFS, SPT, MOPNR, and MWKR from the viewpoint of both dynamic and static situations based on the similarity of schedules before and after variations and based on the rate of makespan deterioration. A new measure of the similarity of schedules is proposed. Guidelines for selecting priority rules, such as avoiding rules that directly use the uncertain information in calculating the priorities, are provided.

• Periodical: Advanced Materials Research (Volumes 889-890)
• Pages: 1189-1202
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.889-890.1189
• Online since: February 2014
• Authors: Haruki Matsuura*, Akiko Asada, Yu Ya Sato
• Keywords: Priority Rule, Robustness, Scheduling, Similarity, Uncertainty

References

[1] Baker, K. R. Introduction to Sequencing and Scheduling, New York: John Wiley & Sons (1974).

[2] Haupt, R., A Survey of Priority Rule-based Scheduling., OR Spektrum 11(1) (1989), p.3–16.

DOI: 10.1007/bf01721162

[3] Ramasesh, R., Dynamic Jobshop Scheduling: A Survey of Simulation Research. , OMEGA 18(1) (1990), p.43–57.

DOI: 10.1016/0305-0483(90)90017-4

[4] Holthaus, O., Rajendran, C., Efficient Jobshop Dispatching Rules: Further Developments., Production Planning and Control 11(2) (2000), p.171–178.

DOI: 10.1080/095372800232379

[5] Pinedo M. and S. Seshadri. 2007. Scheduling and Dispatching., In Handbook of Industrial Engineering (3rd Ed. ), edited by G. Salvendy, 1718–1740, New York: John Wiley.

DOI: 10.1002/9780470172339.ch63

[6] Wu, S.D., Wysk, R.A., An Application of Discrete-event Simulation to On-line Control and Scheduling of Flexible Manufacturing., International Journal of Production Research 27(9) (1989) , p.1603–1623.

DOI: 10.1080/00207548908942642

[7] Aytug, H., S. Bhattacharyya, G. J. Koehler, and J. L. Snowdon. A Review of Machine Learning in Scheduling., IEEE Transactions on Engineering Management 41 (2) (1994), p.165–171.

DOI: 10.1109/17.293383

[8] McKay, K.N., Safayeni, F., Buzacott, J.A., An Information Systems Based Paradigm for Decision Making in Rapidly Changing Industries., Control Engineering Practice 3 (1): (1995), p.77–88.

DOI: 10.1016/0967-0661(94)00067-q

[9] Honkomp, S.J., Mockus, L., Reklaitis, G.V., A Framework for Schedule Evaluation with Processing Uncertainty., Computers and Chemical Engineering 23(4-5) (1999), p.595–609.

DOI: 10.1016/s0098-1354(98)00296-8

[10] Wu, S.D., Byeon, E., Storer, R.H., A Graph-theoretic Decomposition of Jobshop Scheduling Problems to Achieve Scheduling Robustness., Operations Research 47(1) (1999), p.113–124.

DOI: 10.1287/opre.47.1.113

[11] Leon, V.J., Wu, S.D., Storer, R.H., Robustness Measures and Robust Scheduling for Job Shops,. IIE Transactions 26(5) (1993), p.32–43.

DOI: 10.1080/07408179408966626

[12] Jensen, M.T., Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms., IEEE Transactions on Evolutionary Computation 7(3) (2003), p.275–288.

DOI: 10.1109/tevc.2003.810067

[13] Conway, R. W., W. L. Maxwell, and L. W. Miller. Theory of Scheduling. Boston: Addison-Wesley (1967).