Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1999 | Buch

Shop Scheduling: An Overview Kapitel lesen Erstes Kapitel lesen

Multiobjective Scheduling by Genetic Algorithms

verfasst von: Tapan P. Bagchi

Verlag: Springer US

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Multiobjective Scheduling by Genetic Algorithms describes methods for developing multiobjective solutions to common production scheduling equations modeling in the literature as flowshops, job shops and open shops. The methodology is metaheuristic, one inspired by how nature has evolved a multitude of coexisting species of living beings on earth.
Multiobjective flowshops, job shops and open shops are each highly relevant models in manufacturing, classroom scheduling or automotive assembly, yet for want of sound methods they have remained almost untouched to date. This text shows how methods such as Elitist Nondominated Sorting Genetic Algorithm (ENGA) can find a bevy of Pareto optimal solutions for them. Also it accents the value of hybridizing Gas with both solution-generating and solution-improvement methods. It envisions fundamental research into such methods, greatly strengthening the growing reach of metaheuristic methods.
This book is therefore intended for students of industrial engineering, operations research, operations management and computer science, as well as practitioners. It may also assist in the development of efficient shop management software tools for schedulers and production planners who face multiple planning and operating objectives as a matter of course.

Inhaltsverzeichnis

Frontmatter
1. Shop Scheduling: An Overview
Abstract
“Getting the orders out the fastest way possible” is rarely a production manager’s only objective. Customarily, he/she also attempts to minimize tardiness of the jobs, maximize the utilization of expensive capital equipment (furnaces, reactors, rolling mills, printing presses, etc.) and human resources, minimize the mean flow time of the jobs to be done, etc. Such scheduling situations are quite common and these are multiobjective. This book presents the methods for solving multiobjective scheduling situations modeled out of compulsion as single-objective flowshops, job shops and open shops. The methodology is meta-heuristic, one inspired by natural evolution. The method uses innovative variations of “genetic algorithms”—search methods that harness Darwin’s “survival of the fittest” rule and suitable cross-breeding, mutation and niche formation processes that nature is believed to have used to create the multitude of well-adapted and co-habitant life forms on earth.
Tapan P. Bagchi
2. What Are Genetic Algorithms?
Abstract
This chapter describes “genetic algorithms” (commonly called “GAs”)— a set of global search and optimization methods that is fast gaining popularity in solving complex engineering optimization problems with a large search space. GAs belong to the class of meta-heuristic methods known as evolutionary algorithms that model natural evolution processes. GAs evolve solutions to global optimization problems adaptively. Adaptation is a term that we have borrowed from biology implying those structural or behavioral changes in an organism that evolve for their current (or local) utility. Two other meta-heuristic methods that are also used frequently in global search are simulated annealing and tabu search. GAs systematically evolve a population of candidate solutions—with the objective of reaching the “best” solution—by using evolutionary computational processes inspired by genetic variation and natural selection.
Tapan P. Bagchi
3. Calibration of GA Parameters
Abstract
This chapter focuses on a critical dilemma faced in many GA applications: the optimum selection of the different GA parameters to ensure the GA’s rapid convergence—both on-line and off-line (Section 2.9). We address this task early in this text because the satisfactory resolution of it can either make or break the efficacy of the GA, for there is no single makeup of a GA that can uniformly solve all global search problems. In this respect the GA is unlike, for instance, the Newton-Raphson method which finds zeros of almost any polynomial. In particular, the stochastic process that develops as the GA is executing is noted to be affected by the values chosen for the elite fraction (ε) participating in reproduction, crossover probability (pc), mutation probability (pm), population size (ps), etc. The GA’s convergence may be impacted also by the interaction among these parameters. However, no general methodology is presently available to optimize the selection of these parameters. What is even more troublesome is the growing evidence that such “optimum” parameter values may be problem-specific. This chapter presents a robust parameterization procedure based on the statistical design of experiments (DOE) approach (Bagchi and Deb, 1996). A multi-factor constrained optimization problem with known solution is used to illustrate the steps in this proposed method.
Tapan P. Bagchi
4. Flowshop Scheduling
Abstract
A flowshop, as described in Chapter 1, is characterized by unidirectional flow of work with a variety of jobs being processed sequentially in a one-pass manner. A job shop, on the other hand, involves processing on several machines without any “series” structure. In the past four decades extensive research has been done on both flowshop and job shop problems. This chapter evolves a synthesis of the best-known heuristic and meta-heuristic scheduling methods for single objective flowshop problems. We show that a strategy combining the strengths of the different methods produces solutions of good quality—faster than any single solution strategy.
Tapan P. Bagchi
5. Job Shop Scheduling
Abstract
Within the great variety of production scheduling problems that exist, the job shop scheduling problem (JSP) is one that has generated the largest number of studies. It has also earned a reputation for being notoriously difficult to solve. Nevertheless, the JSP illustrates at least some of the demands imposed by a wide array of real world scheduling problems. This chapter summarizes the well-known approaches—algorithmic and heuristic—to solve the single objective job shop problem. Attempts to tackle the multiobjective job shop are still relatively few.
Tapan P. Bagchi
6. Multiobjective Optimization
Abstract
As we pointed out in Chapter 1, rarely is a production manager interested only in getting the orders out the fastest way possible. Typically he/she also wants to minimize tardiness of the jobs from their committed shipping dates, maximize the use of expensive presses, furnaces, reactors and rolling mills, and human resources, minimize the mean flow time of jobs, etc. Such situations crop up everywhere and these are multiobjective. Ironically, however, most quantitative decision making methods confine to single objective optimization. These methods find only the single best alternative with respect to some figure of merit. In this chapter the subject of optimizing multiple objectives is discussed. Methods for solving multiobjective problems and the concept of Pareto optimality are reviewed. The chapter concludes with the citation of the nondominated sorting genetic algorithm (NSGA) (Srinivas and Deb, 1995), a new GA that rapidly discovers Pareto solutions.
Tapan P. Bagchi
7. Niche Formation and Speciation: Foundations of Multiobjective GAs
Abstract
The genesis of GAs, as noted in Chapter 2, was an insightful deduction by several researchers that some aspects of natural evolution could be cast into useful algorithms to solve difficult global search problems in engineering, computer science and economics. Among them was John Holland who began his studies in the 1960s. About the same time, Bremermann (Bremermann, Roghson and Salaff, 1966) independently wrote that mutation, mating and selection of genotypes could be emulated to devise evolutionary computerized schemes that can seek out optima and converge very well. In 1975 Holland published a paradigm for an important process that he termed “adaptation.” He outlined a “genetic plan”—an algorithm to seek out global optima in function optimization (Holland, 1975).
Tapan P. Bagchi
8. The Nondominated Sorting Genetic Algorithm: NSGA
Abstract
Unlike many search methods that develop a single “current best” solution and then try to improve it, a GA maintains a set of possible solutions called the population. At the intuitive level this would suggest that a suitably designed GA might be able to capture the members of the Pareto optimal set of solutions, if Pareto optimality were somehow used as the basis for measuring fitness. In this chapter we describe several approaches to endow GAs with the ability to capture and preserve the Pareto solutions in multiobjective optimization. We then describe the Nondominated Sorting Genetic Algorithm (NSGA), a multiobjective GA designed by Srinivas and Deb (1995) that seeks out Pareto solutions efficiently. A numerical problem, a bi-criteria robust design of an electronic filter, is then solved to illustrate its efficacy.
Tapan P. Bagchi
9. Multiobjective Flowshop Scheduling
Abstract
It was mentioned in Chapter 4 that in sequencing jobs in a flowshop we are likely to confront several different (and often conflicting) management objectives. Consequently, a schedule may have to be evaluated by different types of performance measures. Some of these measures may give importance to completion time (e.g. makespan), some to due date (e.g. mean tardiness, maximum tardiness), and some others to the speed with which the jobs flow (e.g. mean flow time). The simultaneous consideration of these objectives is a multiobjective optimization problem. But, even for a single objective, flowshop sequencing is NP-hard. Therefore, solving even a single objective flowshop problem involving only 15-20 machines and 30-40 jobs by classical optimization methods would be quite difficult.
Tapan P. Bagchi
10. A New Genetic Algorithm for Sequencing the Multiobjective Flowshop
Abstract
This chapter describes a new genetic algorithm that obtains Pareto optimal solutions faster than NSGA. When NSGA is applied to realistic multiobjective problems it is often seen that it lacks somewhat in both on-line performance (converging rapidly to good solutions) and off-line performance (ensuring superior quality of the final solutions). One major reason for this is that NSGA does not preserve the good solutions found from one generation to the next generation. Thus, good (near-optimal) solutions lost in one generation have only a probabilistic chance in NSGA to reappear in the future. Also, the number of final solutions on the Pareto optimal front in NSGA often remains relatively low even with good choice of parameters and even after many generations, unless large population sizes (> 250) are used.
Tapan P. Bagchi
11. A Comparison of Multiobjective Flowshop Sequencing by NSGA and ENGA
Abstract
This chapter presents detailed results of scheduling typical multiobjective flowshop problems involving three simultaneous objectives: (1) minimization of makespan, (2) minimization of mean flow time, and also (3) minimization of the mean tardiness of jobs. Note that no good method—neither analytical nor heuristic—exists in the literature today that finds Pareto-optimal solutions to such problems.
Tapan P. Bagchi
12. Multiobjective Job Shop Scheduling
Abstract
This chapter demonstrates the use of nondominated sorting GAs to schedule multiobjective job shops (JSP). The illustration uses a JSP involving three separate management objectives: (1) minimization of makespan, (2) minimization of mean flow time, and also (3) minimization of the mean tardiness of jobs. As is the case with the flowshop, no method—neither analytical nor heuristic—exists in the literature today for developing Pareto-optimal solutions to this scheduling problem. The two nondominated sorting GAs used here are, as done in the previous chapter, NSGA and ENGA respectively. As is the case with the flowshop, the incorporation of elitism makes the discovery of Pareto optimal schedules more efficient.
Tapan P. Bagchi
13. Multiobjective Open Shop Scheduling
Abstract
This chapter presents the results of scheduling the multiobjective open shop (OSSP). The study is conducted using two conflicting OSSP objectives: (1) minimization of makespan, and (2) minimization of the mean flow time of jobs.
Tapan P. Bagchi
14. Epilog and Directions for Further Work
Abstract
Multi-objective decision making is the typical musing in shop and classroom scheduling, in planning the route for the travelling salesman (even if we do not yet know how to tackle the problem), and in many other problems in management science formulated as combinatorial optimization. This text has described a practical methodology applicable to many such problems where finding Pareto optimal solutions may be of high value.
Tapan P. Bagchi
Backmatter
Metadaten
Titel
Multiobjective Scheduling by Genetic Algorithms
verfasst von
Tapan P. Bagchi
Copyright-Jahr
1999
Verlag
Springer US
Electronic ISBN
978-1-4615-5237-6
Print ISBN
978-1-4613-7387-2
DOI
https://doi.org/10.1007/978-1-4615-5237-6