×

Solving the continuous flow-shop scheduling problem by metaheuristics. (English) Zbl 1052.90030

Summary: Continuous flow-shop scheduling problems circumscribe an important class of sequencing problems in the field of production planning. The problem considered here is to find a permutation of jobs to be processed sequentially on a number of machines under the restriction that the processing of each job has to be continuous with respect to the objective of minimizing the total processing time (flow-time). This problem is \(\mathcal{N} {\mathcal P}\)-hard. We consider the application of different kinds of metaheuristics from a practical point of view, examining the trade-off between running time and solution quality as well as the knowledge and efforts needed to implement and calibrate the algorithms. Computational results show that high quality results can be obtained in an efficient way by applying metaheuristics software components with neither the need to understand their inner working nor the necessity to manually tune parameters.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] Aarts, E. H.L.; Korst, J. H.M.; van Laarhoven, P. J.M., Simulated annealing, (Aarts, E.; Lenstra, J., Local Search in Combinatorial Optimization (1997), Wiley: Wiley Chichester), 91-120 · Zbl 0905.90140
[2] Adiri, I.; Pohoryles, D., Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times, Naval Research Logistics Quarterly, 29, 495-504 (1982) · Zbl 0504.90038
[3] Barr, R. S.; Golden, B. L.; Kelly, J. P.; Resende, M. G.C.; Stewart, W. R., Designing and reporting on computational experiments with heuristic methods, Journal of Heuristics, 1, 9-32 (1995) · Zbl 0853.68154
[4] Battiti, R., Reactive search: Toward self-tuning heuristics, (Rayward-Smith, V.; Osman, I.; Reeves, C.; Smith, G., Modern Heuristic Search Methods (1996), Wiley: Wiley Chichester), 61-83
[5] Bianco, L.; Mingozzi, A.; Ricciardelli, S., The traveling salesman problem with cumulative costs, Networks, 23, 81-91 (1993) · Zbl 0821.90121
[6] Bonney, M. C.; Gundry, S. W., Solutions to the constrained flowshop sequencing problem, Operations Research Quarterly, 24, 869-883 (1976) · Zbl 0345.90020
[7] Cerny, V., Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, 45, 41-51 (1985) · Zbl 0534.90091
[8] Chen, C.-L.; Neppalli, R. V.; Aljaber, N., Genetic algorithms applied to the continuous flow shop problem, Computers and Industrial Engineering, 30, 919-929 (1996)
[9] Connolly, D., General purpose simulated annealing, Journal of the Operational Research Society, 43, 495-505 (1992) · Zbl 0756.90066
[10] Culberson, J. C., On the futility of blind search: An algorithmic view of “no free lunch”, Evolutionary Computation, 6, 109-127 (1998)
[11] Dudek, R. A.; Panwalkar, S. S.; Smith, M. L., The lessons of flowshop scheduling research, Operations Research, 40, 7-13 (1992) · Zbl 0825.90554
[12] Duin, C. W.; Voß, S., The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs, Networks, 34, 181-191 (1999) · Zbl 0980.90094
[13] Fink, A., 2000. Software-Wiederverwendung bei der Lösung von Planungsproblemen mittels Meta-Heuristiken. Shaker, Aachen; Fink, A., 2000. Software-Wiederverwendung bei der Lösung von Planungsproblemen mittels Meta-Heuristiken. Shaker, Aachen
[14] Fink, A.; Schneidereit, G.; Voß, S., Solving general ring network design problems by meta-heuristics, (Laguna, M.; González Velarde, J., Computing Tools for Modeling, Optimization and Simulation (2000), Kluwer: Kluwer Boston), 91-113
[15] Fink, A.; Voß, S., Applications of modern heuristic search methods to pattern sequencing problems, Computers and Operations Research, 26, 17-34 (1999) · Zbl 0957.90044
[16] Fink, A.; Voß, S., Generic metaheuristics application to industrial engineering problems, Computers and Industrial Engineering, 37, 281-284 (1999)
[17] Fink, A.; Voß, S., HotFrame: A heuristic optimization framework, (Voß, S.; Woodruff, D., Optimization Software Class Libraries (2002), Kluwer: Kluwer Boston), 81-154
[18] Fink, A., Voß, S., Woodruff, D.L., 1999. An adoption path for intelligent heuristic search componentware. In: Rolland, E. Umanath, N. (Eds.), Proceedings of the 4th INFORMS Conference on Information Systems and Technology. INFORMS, Linthicum, pp. 153-168; Fink, A., Voß, S., Woodruff, D.L., 1999. An adoption path for intelligent heuristic search componentware. In: Rolland, E. Umanath, N. (Eds.), Proceedings of the 4th INFORMS Conference on Information Systems and Technology. INFORMS, Linthicum, pp. 153-168
[19] Fischetti, M.; Laporte, G.; Martello, S., The delivery man problem and cumulative matroids, Operations Research, 41, 1055-1076 (1993) · Zbl 0791.90062
[20] Gangadharan, R.; Rajendran, C., Heuristic algorithms for scheduling in the no-wait flowshop, International Journal of Production Economics, 32, 285-290 (1993)
[21] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer: Kluwer Dordrecht · Zbl 0930.90083
[22] Gouveia, L.; Voß, S., A classification of formulations for the (time-dependent) traveling salesman problem, European Journal of Operational Research, 83, 69-82 (1995) · Zbl 0903.90170
[23] Gupta, J. N.D., Optimal flowshop schedules with no intermediate storage space, Naval Research Logistics Quarterly, 23, 235-243 (1976) · Zbl 0328.90038
[24] Hajek, B., Cooling schedules for optimal annealing, Mathematics of Operations Research, 13, 311-329 (1988) · Zbl 0652.65050
[25] Hall, N. G.; Sriskandarajah, C., A survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510-525 (1996) · Zbl 0864.90060
[26] Hooker, J. N., Needed: An empirical science of algorithms, Operations Research, 42, 201-212 (1994) · Zbl 0805.90119
[27] Hooker, J. N., Testing heuristics: We have it all wrong, Journal of Heuristics, 1, 33-42 (1995) · Zbl 0853.68155
[28] Huang, M.D., Romeo, F., Sangiovanni-Vincentelli, A., 1986. An efficient general cooling schedule for simulated annealing. In: Proceedings of the ICCAD-86: IEEE International Conference on Computer-Aided Design, Santa Clara, pp. 381-384; Huang, M.D., Romeo, F., Sangiovanni-Vincentelli, A., 1986. An efficient general cooling schedule for simulated annealing. In: Proceedings of the ICCAD-86: IEEE International Conference on Computer-Aided Design, Santa Clara, pp. 381-384
[29] Johnson, D. S.; Aragon, C. R.; McGeoch, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation; part 1, Graph partitioning, Operations Research, 37, 865-892 (1989) · Zbl 0698.90065
[30] King, J. R.; Spachis, A. S., Heuristics for flow-shop scheduling, International Journal of Production Research, 18, 343-357 (1980)
[31] Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[32] Lucena, A., Time-dependent traveling salesman problem-the deliveryman case, Networks, 20, 753-763 (1990) · Zbl 0744.90063
[33] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical Programming, 34, 111-124 (1986) · Zbl 0581.90061
[34] Nievergelt, J., Complexity, algorithms, programs, systems: The shifting focus, Journal of Symbolic Computation, 17, 297-310 (1994) · Zbl 0822.68051
[35] Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 421-451 (1993) · Zbl 0775.90153
[36] (Osman, I. H.; Kelly, J. P., Meta-Heuristics: Theory and Applications (1996), Kluwer: Kluwer Boston)
[37] Papadimitriou, C. H.; Kanellakis, P. C., Flowshop scheduling with limited temporary storage, Journal of the Association of Computing Machinery, 27, 533-549 (1980) · Zbl 0475.68014
[38] Picard, J.-C.; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Operations Research, 26, 86-110 (1978) · Zbl 0371.90066
[39] Rajendran, C., A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the Operational Research Society, 45, 472-478 (1994) · Zbl 0799.90060
[40] Rajendran, C.; Chaudhuri, D., Heuristic algorithms for continuous flow-shop problem, Naval Research Logistics, 37, 695-705 (1990) · Zbl 0707.90052
[41] Reddi, S. S.; Ramamoorthy, C. V., On the flow-shop sequencing problem with no wait in process, Operational Research Quarterly, 23, 323-331 (1972) · Zbl 0238.90080
[42] (Reeves, C. R., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell: Blackwell Halsted) · Zbl 0942.90500
[43] Reisman, A.; Kumar, A.; Motwani, J., Flowshop scheduling/sequencing research: A statistical review of the literature, 1952-1994, IEEE Transactions on Engineering Management, 44, 316-329 (1997)
[44] Sahni, S.; Gonzales, T., \(P\)-complete approximation problems, Journal of the Association of Computing Machinery, 23, 555-565 (1976) · Zbl 0348.90152
[45] Szwarc, W., A note on the flow-shop problem without interruptions in job processing, Naval Research Logistics Quarterly, 28, 665-669 (1981) · Zbl 0535.90046
[46] Taillard, E., Benchmarks for basic scheduling instances, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052
[47] van Deman, J. M.; Baker, K. R., Minimizing mean flowtime in the flow shop with no intermediate queues, AIIE Transactions, 6, 28-34 (1974)
[48] van der Veen, J. A.A.; van Dal, R., Solvable cases of the no-wait flow-shop scheduling problem, Journal of the Operational Research Society, 42, 971-980 (1991) · Zbl 0744.90044
[49] van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), Reidel: Reidel Dordrecht · Zbl 0643.65028
[50] (Voß, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1999), Kluwer: Kluwer Boston)
[51] Wismer, D. A., Solution of the flowshop sequencing problem with no intermediate queues, Operations Research, 20, 695-705 (1972) · Zbl 0241.90031
[52] Wolpert, D. H.; Macready, W. G., No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, 1, 67-82 (1997)
[53] Woodruff, D. L.; Zemel, E., Hashing vectors for tabu search, Annals of Operations Research, 41, 123-138 (1993) · Zbl 0775.90294
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.