×

Genetic algorithms for the two-stage bicriteria flowshop problem. (English) Zbl 0943.90584

Summary: This paper considers the two-stage bicriteria flowshop scheduling problem with the objective of minimizing the total flow time subject to obtaining the optimal makespan. In view of the NP-hard nature of the problem, two Genetic Algorithms (GA) based approaches are proposed to solve the problem. The effectiveness of the proposed GA based approaches is demonstrated by comparing their performance with the only known heuristic for the problem. The computational experiments show that the proposed GA based approaches are effective in solving the problem and recommend that the proposed GA based approaches are useful for solving the multi-machine, multicriteria scheduling problems.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Azizoglu, M.; Kondakci, S.; Kirca, O., Bicriteria scheduling problem involving total tardiness and total earliness penalties, International Journal of Production Economics, 23, 17-24 (1991)
[2] Bagchi, U., Simultaneous minimization of mean and variation of flow time and waiting time in single machine systems, Operations Research, 37, 118-125 (1989) · Zbl 0661.90046
[3] Barnes, J. W.; Vanston, L. K., Scheduling jobs with linear delay penalties and sequence dependent setup costs, Operations Research, 29, 146-160 (1981) · Zbl 0454.90037
[4] Bianco, L.; Ricciardelli, S., Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Research Logistics Quarterly, 29, 151-167 (1982) · Zbl 0539.90044
[5] Biegal, J. E.; Davern, J. J., Genetic algorithms and job shop scheduling, Computers and Industrial Engineering, 19 (1990)
[6] Cenna, A. A.; Tabucanon, M. T., Bicriteria scheduling problem in a job shop with parallel processors, International Journal of Production Economics, 25, 95-101 (1991)
[7] Chand, S.; Schneeberger, H., A note on the single machine scheduling problem with weighted completion time and maximum allowable tardiness, Naval Research Logistics Quarterly, 33, 551-557 (1986) · Zbl 0601.90079
[8] Chen, C. L.; Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems, European Journal of Operational Research, 70, 115-125 (1993) · Zbl 0795.90032
[9] Chen, C. L.; Bulfin, R. L., Complexity of multiple machine multiple criteria scheduling problems, (Proceedings of the Third IERC. Proceedings of the Third IERC, Atlanta, GA (1994))
[10] Chen, C. L.; Vempati, V. S.; Aljaber, N., An application of genetic algorithms for flow shop problems, European Journal of Operational Research, 80, 389-396 (1995)
[11] Cleveland, G. A.; Smith, S. F., Using genetic algorithms to schedule flow shop release, (Proceedings of the Third International Conference on Genetic Algorithms Applications (1989)), 160-169
[12] Daniel, R. L., Multi-objective flow shop scheduling, Naval Research Logistics Quarterly, 37, 981-995 (1992) · Zbl 0825.90551
[13] Davis, L., (Handbook on Genetic Algorithms (1987), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[14] DeJong, K. A., Analysis of the behavior of a class of genetic adaptive systems, (Ph.D. Dissertation (1975), University of Michigan)
[15] Dileepan, P.; Sen, T., Bicriterion state scheduling research for a single machine, Omega, 16, 53-59 (1988)
[16] Emmons, H., One machine sequencing to minimize mean flow time with minimum number of tardy, Naval Research Logistics Quarterly, 22, 585-592 (1975) · Zbl 0315.90032
[17] Goldberg, D. E.; Lingle, R., Alleles, loci and the Travelling Salesman Problem, (Proceedings of International Conference on Genetic Algorithms and their Applications (1985), Carnegie-Mellon University: Carnegie-Mellon University Pittsburgh, PA), 154-159
[18] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[19] Grefenstette, J. J., Optimized control of parameters for genetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics, 16, 122-128 (1986)
[20] Grefenstette, J. J., Incorporating problem specific knowledge into genetic algorithms, (Davis, L., Genetic Algorithms and Simulated Annealing (1987)), Los Altos, CA
[21] Heck, H.; Roberts, S., A note on the extension of a result on scheduling with secondary criteria, Naval Research Logistics Quarterly, 19, 403-405 (1972) · Zbl 0249.90033
[22] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI
[23] Holland, J. H., Genetic algorithms, Scientific American, 117-125 (July 1992)
[24] Johnson, S. M., Optimal two- and three-stage production schedules with set-up times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[25] Keeney, R. L.; Raiffa, H., Decision with Multiple Objectives: Preference and Value Tradeoffs (1976), Wiley: Wiley New York · Zbl 0488.90001
[26] (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Travelling Salesman Problem (1985), Wiley: Wiley New York) · Zbl 0563.90075
[27] Miyazaki, S., One machine scheduling problem with dual criteria, Journal of the Operations Research Society of Japan, 24, 37-51 (1981) · Zbl 0453.90045
[28] Nelson, R. T.; Sarin, R. K.; Daniels, R. L., Scheduling with multiple performance measures: The one machine case, Management Science, 32, 464-479 (1986) · Zbl 0603.90070
[29] Neppalli, V. R.; Chen, C. L.; Aljaber, N. J., An effective heuristic for the flow shop problem with weighted tardiness, (Proceedings of the Third Industrial Engineering Research Conference (1994)), 634-638
[30] Rajeev, S.; Krishnamoorthy, C. S., Discrete optimization of structures using genetic algorithms, Journal of Structural Engineering, 15, 1233-1250 (1992)
[31] Rajendran, C., Two-stage flowshop scheduling problem with bicriteria, Journal of the Operational Research Society, 43, 871-884 (1992) · Zbl 0757.90037
[32] Ruiz-Diaz, F.; French, S., A survey of multi-objective combinatorial scheduling, (French, S.; Thomas, L. C.; Hartley, R.; White, D. J., Multi-objective Decision Making (1983), Academic Press: Academic Press New York), 59-77
[33] Sen, T.; Gupta, S. K., A branch-and-bound procedure to solve a bicriterion scheduling problem, IIE Transactions, 15, 84-88 (1983)
[34] Schaffer, J. D., Multiple objective optimization with vector evaluated genetic algorithms, (Proceedings of International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann New York), 93-100
[35] Shaffer, J. D.; Caruna, R. A.; Eshelman, L. J.; Das, R., A study of control parameters affecting online performance of genetic algorithms for function optimization, (Schaffer, J. D., Proceedings of the Third International Conference on Genetic Algorithm (1989), Morgan Kaufmann: Morgan Kaufmann New York), 51-60
[36] Shanthikumar, J. G.; Scheduling, njobs on one machine to minimize the maximum tardiness with minimum number of tardy, Computers & Operations Research, 10, 255-266 (1983)
[37] Smith, W. E., Various optimizers for single state production, Naval Research Logistics Quarterly, 3, 59-66 (1957)
[38] Tzafestas, S.; Triantafyllakis, A., Deterministic scheduling in computing and manufacturing systems: A survey of models and algorithms, Mathematics and Computers in Simulation, 35, 397-434 (1993)
[39] Van Wassenhove, L. N.; Baker, K. R., A bicriterion approach to time/cost trade-offs in sequencing, European Journal of Operational Research, 11, 48-54 (1982) · Zbl 0482.90043
[40] Van Wassenhove, L. N.; Gelders, L. F., Solving a bicriterion scheduling problem, European Journal of Operational Research, 4, 42-48 (1980) · Zbl 0418.90054
[41] Vempati, V. S.; Chen, C. L.; Bullington, S. F., An application of genetic algorithms to the Flow Shop Problem, (Proceedings of 15th International Conference of Computers and Industrial Engineering (1993))
[42] Vickson, R. G., Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine, Operations Research, 28, 1155-1167 (1980) · Zbl 0449.90054
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.