Solving Permutation Flow shop Problem by the Regulations of Columnar Entries in the Processing Times Matrix

Author
Shahriar Farahmand Rad
Payame Noor University, Tehran
Abstract
Scheduling theory and permutation therein are two important subjects in discrete operation research. In this paper, a new heuristic algorithm is proposed for solving permutation flow shop problem by using regulations of columnar entries in the processing times matrix. There are jobs to be processed on machines with deterministic processing times and the object is obtaining the minimum of the total time to complete the schedule (makespan). This is not solvable in polynomial time. First, an initial suitable sequence of jobs is determined similar to many heuristics. For this, the matrix is made such that every determines the measure of the fitness for the location of the th old row in the th new position. Thereafter, the Bellman Esogbue Nabeshima theorem is used. The presented algorithm is compared with the NEH (the best well-known existing method). This comparison is made by the Taillard’s standard test problems. Computational results demonstrate that the heuristic algorithm is better than some of the proposed heuristics known so far and it is superior with respect to others in a number of Taillard instances. As a result, it is almost as good as NEH and is very promising for the problem. On the basis of the structure of the proposed algorithm, it can perform a role as meta-heuristic.
Keywords
Scheduling
Permutation flow shop
Heuristics
Initial sequences
Time matrix
Makespan
NEH
Taillard’s benchmark
[1] Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.

[2] Page, E. S. (1961). An approach to the scheduling of jobs on machines. Journal of the Royal Statistical Society: Series B (Methodological), 23(2), 484-492.

[3] Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the Operational Research Society, 16(1), 101-107.

[4] Petrov. V. A. (1966). Flow Line Group, production planning. Business Publications, London.

[5] Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management science, 16(10), B-630.

[6] Gupta, J. N. (1971). A functional heuristic algorithm for the flowshop scheduling problem. Journal of the Operational Research Society, 22(1), 39-47.

[7] Dannenbring, D. G. (1977). An evaluation of flow shop sequencing heuristics. Management science, 23(11), 1174-1182.

[8] King, J. R., & Spachis, A. S. (1980). Heuristics for flow-shop scheduling. International Journal of Production Research, 18(3), 345-357.

[9] STINSON, J. P., & SMITH, A. W. (1982). A heuristic proǵramminǵ procedure for sequencinǵ the static flowshop. The International Journal Of Production Research, 20(6), 753-764.

[10] Nawaz, M., Enscore Jr, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.

[11] Hundal, T. S., & Rajgopal, J. (1988). An extension of Palmer's heuristic for the flow shop scheduling problem. International Journal of Production Research, 26(6), 1119-1124.

[12] Widmer, M., & Hertz, A. (1989). A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, 41(2), 186-193.

[13] Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European journal of Operational research, 47(1), 65-74.

[14] Ho, J. C., & Chang, Y. L. (1991). A new heuristic for the n-job, M-machine flow-shop problem. European Journal of Operational Research, 52(2), 194-202.

[15] Sarin, S., & Lefoka, M. (1993). Scheduling heuristic for the n-jobm-machine flow shop. Omega, 21(2), 229-234.

[16] Moccellin, J. V. (1995). A new heuristic method for the permutation flow shop scheduling problem. Journal of the Operational research Society, 46(7), 883-886.

[17] Lai, T. C. (1996). A note on heuristics of flow-shop scheduling. Operations Research, 44(4), 648-652.

[18] Koulamas, C. (1998). A new constructive heuristic for the flowshop scheduling problem. European Journal of Operational Research, 105(1), 66-71.

[19] Suliman, S. M. A. (2000). A two-phase heuristic approach to the permutation flow-shop scheduling problem. International Journal of Production Economics, 64(1), 143-152.

[20] Framinan, J. M., Leisten, R., & Rajendran, C. (2003). Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem. International Journal of Production Research, 41(1), 121-148.

[21] Kurz, M. E., & Askin, R. G. (2004). Scheduling flexible flow lines with sequence-dependent setup times. European Journal of Operational Research, 159(1), 66-82.

[22] Leung, J. Y. T., Li, H., & Pinedo, M. (2005). Order scheduling in an environment with dedicated resources in parallel. Journal of Scheduling, 8(5), 355-386.

[23] Allahverdi, A., & Al-Anzi, F. S. (2006). A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers & Operations Research, 33(4), 1056-1080.

[24] Alaykýran, K., Engin, O., & Döyen, A. (2007). Using ant colony optimization to solve hybrid flow shop scheduling problems. The international journal of advanced manufacturing technology, 35(5), 541-550.

[25] Kalczynski, P. J., & Kamburowski, J. (2008). An improved NEH heuristic to minimize makespan in permutation flow shops. Computers & Operations Research, 35(9), 3001-3008.

[26] Rad, S. F., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2), 331-345.

[27] Ancău, M. (2012). On Solving Flowshop Scheduling Problems. Proceedings of the Romanian Academy. Series A, 13(1), 71-79.

[28] Malik, A., & Dhingra, A. K. (2013). Comparative analysis of heuristics for make span minimizing in flow shop scheduling. International Journal of Innovations in Engineering and Technology, 2(4), 263-269.

[29] Xu, J., Yin, Y., Cheng, T. C. E., Wu, C. C., & Gu, S. (2014). An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem. International Journal of Production Research, 52(4), 1188-1199.

[30] Liu, W., Jin, Y., & Price, M. (2016). A new Nawaz–Enscore–Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time. Engineering Optimization, 48(10), 1808-1822.

[31] Brum, A., & Ritt, M. (2018, July). Automatic Design of Heuristics for Minimizing the Makespan in Permutation Flow Shops. In 2018 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE.

[32] Nurdiansyah, R., Rijanto, O. A. W., Santosa, B., & Wiratno, S. E. (2019). An Improved Differential Evolution Algorithm for Permutation Flow Shop Scheduling Problem. International Journal of Operations Research, 16(2), 37-44.

[33] Sauvey, C., & Sauer, N. (2020). Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion. Algorithms, 13(5), 112.

[34] Bellman, Richard, Augustine O. Esogbue, and Ichiro Nabeshima. Mathematical Aspects of Scheduling and Applications: Modern Applied Mathematics and Computer Science. Vol. 4. Elsevier, 2014.

[35] Farahmand Rad, S. (2021). An effective new heuristic algorithm for solving permutation flow shop scheduling problem. Transactions on Combinatorics (in press).