Minimizing The Number of Tardy Jobs in Hybrid Flow Shops with Non-Identical Multiple Processors

Authors

  • Daryl Santos Binghamton University
  • Ivan Roa

DOI:

https://doi.org/10.37266/ISER.2018v6i1.pp62-73

Abstract

Two-stage hybrid flow shops (a.k.a., flow shops with multiple processors (FSMPs)) are studied wherein the multiple processors at a stage are non-identical, but related (a.k.a., uniform) in their processing speeds.   The impact of ten different dispatching procedures on a due-date based criterion (specifically, the number of tardy jobs) is analyzed over a set of 1,800 problems of varying configurations wherein the number of jobs per problem is between 20 and 100 and their due dates are randomly assigned.  Results indicate that the modified due date (MDD), earliest due date (EDD), slack (SLK), shortest processing time (SPT), and least work remaining (LWR) rules are statistically inseparable but yield superior performance to the other rules included in this study.  The longest processing time (LPT) and most work remaining (MWR) rules provide the poorest performance.

References

Brah, S.A. (1988). Scheduling in a Flow Shop with Multiple Processors, Unpublished Ph.D. Dissertation, University of Houston, Houston, TX.

Brah, S.A. and Loo, L.L. (1999). Heuristics for Scheduling in a Flow Shop with Multiple Processors. European Journal of Operational Research, 113, pp. 113-122.

Cheng, T.C. (1986). Optimal Due Date Assignment in a Job Shop. International Journal of Production Research, 24, pp. 503-515.

Conway, R.W. (1964). An Investigation of Priority Assignment in a Job Shop. RAND Corporation Memorandum RM-3789-PR.

Conway, R.W., Maxwell, W.L., and Miller, L.W. (1967), Theory of Scheduling, Addison-Wesley, Reading, Massachusetts.

Dessouky, M.I., Lageweg, B.J., Lenstra, J.K., and Van de Velde, S.L. (1990). Scheduling Identical Jobs on Uniform Parallel Machines. Statistical Neerlandica, 44, pp.115-123.

Friesen, D.K. and Langston, M,A. (1983). Bounds for Multifit Scheduling on Uniform Processors. SIAM Journal on Computing, 12, pp. 60-70.

Guinet, A. (1995). Scheduling Independent Jobs on Uniform Parallel Machines to Minimize Tardiness Criteria. Journal of Intelligent Manufacturing, 6, pp. 95-103.

Hunsucker, J.L. and Shah, J.R. (1992). Performance of Priority Rules in a Due Date Flow Shop. Omega, 20, pp. 73-89.

Hunsucker, J.L. and Shah, J.R. (1994). Comparative Performance Analysis of Priority Rules in a Constrained Flow Shop with Multiple Processors Environment. European Journal of Operational Research, 72, pp. 102-114.

Martinez, J. (1992). Due Date Assignment Methods and Dispatching Rules in a Flow Shop with Multiple Processors. M.S.I.E. Thesis, University of Houston, Houston, TX.

Morton, T.E and Pentico, D.W. (1993). Heuristic Scheduling Systems: with Applications to Production Systems and Project Management, John Wiley and Sons, New York.

Pinedo, M. (2002). Scheduling: Theory, Algorithms, and Systems, 2nd Ed., Prentice Hall, Englewood Cliffs, New Jersey.

Roa (2000). A Study of Flow Shops with Non-Identical Multiple Processors. Ph.D.S.S. Dissertation. Binghamton University, Binghamton, NY.

Roa and Santos (1999). Lower Bounds for Two-Stage Hybrid Flow Shops with Non-identical Multiple Processors. Proceedings of the 4th International Conference on Industrial Engineering, Theory, and Applications, San Antonio, Texas.

Salvador, M.S. (1973). A Solution to a Special Case of Flow Shop Scheduling Problems. In S.E. Elmaghraby (ed.), Symposium of the Theory of Scheduling and Applications, Springer-Verlag, New York.

Santos, D.L. (1990). The Effect of Varying the Underlying Processing Times in the Single Stage Multiprocessor Scheduling Environment. M.S.I.E. Thesis, University of Houston, Houston, Tx.

Santos, D.L. (1993). A Study of Makespans in Flow Shops with Multiple Processors. Ph.D.I.E. Dissertation, University of Houston, Houston, TX.

Santos, D.L., Hunsucker, J.L., and Deal, D.E. (1996). An Evaluation of Sequencing Heuristics in Flow Shops with Multiple Processors. Computers and Industrial Engineering, 30, pp. 681-692.

Santos, D.L., Hunsucker, J.L., and Deal, D.E. (2001). Makespan Improvement in Flow Shop with Multiple Processors via an Exchange Heuristic. Production Planning and Control, 12, pp. 283-295.

Santos, D.L. and Roa, I. (2007). Mixed-Integer Linear Programming Models for Managing Hybrid Flow Shops with Uniform, Non-Identical Multiple Processors. Asia Pacific Management Review, 12(2), pp. 95-100.

Schellhase, J.C. (1996). The Placement of an Additional Processor in a Flow Shop with Multiple Processors. Ph.D.I.E. Dissertation, University of Houston, Houston, TX.

Shah, J.R. (1989). Heuristic Programming Study of a Constrained Flow Shop with Multiple Processors. MS.I.E. Thesis, University of Houston, Houston, TX.

Sule, D.R. (1996). Industrial Scheduling, PWS Publishing Company, Boston, MA.

Tamimi, S.A. and Rajan, V.N. (1997). Reduction of Total Weighted Tardiness on Uniform Machines with Sequence Dependent Setups. 6th Industrial Engineering Research Conference Proceedings, Washington, DC, pp. 181-185.

Younes, N., Santos, D., and Maria, A. (1998). A Simulated Annealing Approach to Scheduling in a Flow Shop with Multiple Processors. 7th Industrial Engineering Research Conference Proceedings, Banff, Canada, 8pp.

Published

2018-11-21

How to Cite

Santos, D., & Roa, I. (2018). Minimizing The Number of Tardy Jobs in Hybrid Flow Shops with Non-Identical Multiple Processors. Industrial and Systems Engineering Review, 6(1), 62-73. https://doi.org/10.37266/ISER.2018v6i1.pp62-73