A new multi-objective genetic algorithm applied to hot-rolling process

A new genetic algorithms based multi-objective optimization algorithm (NMGA) has been developed during study. It works on a neighborhood concept in the functional space, utilizes the ideas on weak dominance and ranking and uses its own procedures for population sizing. The algorithm was successfully tested with some standard test functions, and when applied to a real-life data of the hot-rolling campaign of an integrated steel plant, it outperformed another recently developed multi-objective evolutionary algorithm.     

A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.     

Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm

Relative to job-shop scheduling problems that optimize makespan or flow time, due-date-related problems are usually much more computationally complex and are classified as strongly NP-hard. In this paper, a hybrid framework integrating a heuristic and a genetic algorithm (GA) is utilized for job-shop scheduling to minimize weighted tardiness. For each new generation of schedules, the GA determines the first operation of each machine, and the heuristic determines the assignment of the remaining operations. Schedules with inferior tardiness are discarded before the next round of evolution. Extensive numerical experiments were conducted for different levels of due-date tightness. The results show that the hybrid framework performs significantly better than does either a heuristic or GA alone. It is also found to be superior to a well-recognized heuristic improvement procedure (lead-time iterations). Specifically, the combination of the R&M heuristic and a GA outperforms a number of heuristics commonly used to minimize total tardiness and weighted total tardiness; this combination is, however, outperformed by the heuristic of Kreipl [Kreipl, S., 2000. A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling 3, 125–138]. We also develop a generalized hybrid framework that can adapt to different job-shop problems—with or without sequence-dependent setups and with different objectives (e.g., makespan, tardiness, flow time). The new framework allows the interaction of parallel evolutions, extending the GA-heuristic environment to the solving of multi-objective scheduling problems.     

A multi-objective genetic algorithm for cardinality constrained fuzzy portfolio selection

This paper presents a new procedure that extends genetic algorithms from their traditional domain of optimization to fuzzy ranking strategy for selecting efficient portfolios of restricted cardinality. The uncertainty of the returns on a given portfolio is modeled using fuzzy quantities and a downside risk function is used to describe the investor's aversion to risk. The fitness functions are based both on the value and the ambiguity of the trapezoidal fuzzy number which represents the uncertainty on the return. The soft-computing approach allows us to consider uncertainty and vagueness in databases and also to incorporate subjective characteristics into the portfolio selection problem. We use a data set from the Spanish stock market to illustrate the performance of our approach to the portfolio selection problem.     

Solving a concrete sleepers production scheduling by genetic algorithms

PRECON S.A. is a manufacturing company devoted to produce prefabricated concrete parts for several industries as railway transportation and agricultural industries. Recently, PRECON S.A. signed a contract with RENFE, the Spanish National Railway Company, to manufacture pre-stressed concrete sleepers for the sidings of the new railways of the high speed train (AVE). The scheduling problem associated with the manufacturing process of the sleepers is very complex, since this involves several constraints and objectives. These constraints are related to production capacity, the quantity of available moulds, demand satisfaction and other operational constraints. The two main objectives are related to the way to maximize the utilization of manufacturing resources and minimize mould movements. We developed a deterministic crowding genetic algorithm for this multiobjective problem. The algorithm has proved to be a powerful and flexible tool to solve large-scale instances of this real and complex scheduling problem.     

Quality inspection scheduling for multi-unit service enterprises

The traveling salesman problem is a classic NP-hard problem used to model many production and scheduling problems. The problem becomes even more difficult when additional salesmen are added to create a multiple traveling salesman problem (MTSP). We consider a variation of this problem where one salesman visits a given set of cities in a series of short trips. This variation is faced by numerous franchise companies that use quality control inspectors to ensure properties are maintaining acceptable facility and service levels. We model an actual franchised hotel chain using traveling quality inspectors to demonstrate the technique. The model is solved using a commercially available genetic algorithm (GA) tool as well as a custom GA program. The custom GA is proven to be an effective method of solving the proposed model.     

Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization

In this paper, a HGA (hybrid genetic algorithm) is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are known to be NP-hard. One of the chromosomes in the initial population is constructed by a suitable heuristic and the others are yielded randomly. An artificial chromosome is generated by a weighted simple mining gene structure, with which a new crossover operator is presented. Additionally, two effective heuristics are adopted as local search to improve all generated chromosomes in each generation. The HGA is compared with one of the most effective heuristics and a recent meta-heuristic on 120 benchmark instances. Experimental results show that the HGA outperforms the other two algorithms for all cases. Furthermore, HGA obtains 115 best solutions for the benchmark instances, 92 of which are newly discovered.     

A genetic algorithm for resource investment project scheduling problem,tardiness permitted with penalty

In this paper a genetic algorithm for solving a class of project scheduling problems, called Resource Investment Problem, is presented. Tardiness of project is permitted with defined penalty. Elements of algorithm such as chromosome structure, unfitness function, crossover, mutation, immigration and local search operations are explained.     

A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem

This paper presents a genetic algorithms (GA) simulation approach in solving a multi-attribute combinatorial dispatching (MACD) decision problem in a flow shop with multiple processors (FSMP) environment. The simulation is capable of modeling a non-linear and stochastic problem. GA are one of the commonly used metaheuristics and are a proven tool for solving complex optimization problems. The proposed GA simulation approach addresses a complex MACD problem. Its solution quality is illustrated by a case study from a multi-layer ceramic capacitor (MLCC) manufacturing plant. Because GA search results are often sensitive to the search parameters, this research optimized the GA parameters by using regression analysis. Empirical results showed that the GA simulation approach outperformed several commonly used dispatching rules. The improvements are ranging from 33% to 61%. On the other hand, the increased shop-floor-control complexity may hinder the implementation of the system. Finally, future research directions are discussed.     

A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem

This paper presents a genetic algorithm for solving the resource-constrained project scheduling problem. The innovative component of the algorithm is the use of a magnet-based crossover operator that can preserve up to two contiguous parts from the receiver and one contiguous part from the donator genotype. For this purpose, a number of genes in the receiver genotype absorb one another to have the same order and contiguity they have in the donator genotype. The ability of maintaining up to three contiguous parts from two parents distinguishes this crossover operator from the powerful and famous two-point crossover operator, which can maintain only two contiguous parts, both from the same parent. Comparing the performance of the new procedure with that of other procedures indicates its effectiveness and competence.     

A memetic algorithm for multi-objective dynamic location problems

This paper describes a new multiobjective interactive memetic algorithm applied to dynamic location problems. The memetic algorithm integrates genetic procedures and local search. It is able to solve capacitated and uncapacitated multi-objective single or multi-level dynamic location problems. These problems are characterized by explicitly considering the possibility of a facility being open, closed and reopen more than once during the planning horizon. It is possible to distinguish the opening and reopening periods, assigning them different coefficient values in the objective functions. The algorithm is part of an interactive procedure that asks the decision maker to define interesting search areas by establishing limits to the objective function values or by indicating reference points. The procedure will be applied to some illustrative location problems.     

A hybrid genetic algorithm for the resource-constrained project scheduling problem

In this paper we propose a Hybrid Genetic Algorithm (HGA) for the Resource-Constrained Project Scheduling Problem (RCPSP). HGA introduces several changes in the GA paradigm: a crossover operator specific for the RCPSP; a local improvement operator that is applied to all generated schedules; a new way to select the parents to be combined; and a two-phase strategy by which the second phase re-starts the evolution from a neighbour’s population of the best schedule found in the first phase. The computational results show that HGA is a fast and high quality algorithm that outperforms all state-of-the-art algorithms for the RCPSP known by the authors of this paper for the instance sets j60 and j120. And that it is competitive with other state-of-the-art heuristics for the instance set j30.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

A multi-objective lead time control problem in multi-stage assembly systems using genetic algorithms

In this paper, we develop a multi-objective model to optimally control the lead time of a multi-stage assembly system, using genetic algorithms. The multi-stage assembly system is modelled as an open queueing network. It is assumed that the product order arrives according to a Poisson process. In each service station, there is either one or infinite number of servers (machines) with exponentially distributed processing time, in which the service rate (capacity) is controllable. The optimal service control is decided at the beginning of the time horizon. The transport times between the service stations are independent random variables with generalized Erlang distributions. The problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. The objective functions are the total operating costs of the system per period (to be minimized), the average lead time (min), the variance of the lead time (min) and the probability that the manufacturing lead time does not exceed a certain threshold (max). Finally, we apply a genetic algorithm with double strings using continuous relaxation based on reference solution updating (GADSCRRSU) to solve this multi-objective problem, using goal attainment formulation. The results are also compared against the results of a discrete-time approximation technique to show the efficiency of the proposed genetic algorithm approach.     

Multi-objective genetic algorithm for single machine scheduling problem under fuzziness

This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty. The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life problem of a manufacturing pottery company.     

Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete

The coordination of just-in-time production and transportation in a network of partially independent facilities to guarantee timely delivery to distributed customers is one of the most challenging aspect of supply chain management. From a theoretical perspective, the timely production/distribution can be viewed as a hybrid combination of planning, scheduling and routing problems, each notoriously affected by nearly prohibitive combinatorial complexity. From a practical viewpoint, the problem calls for a trade-off between risks and profits. This paper focuses on the ready-mixed concrete delivery: in addition to the mentioned complexity, strict time-constraints forbid both earliness and lateness of the supply. After developing a detailed model of the considered problem, we propose a novel meta-heuristic approach based on a hybrid genetic algorithm combined with constructive heuristics. A detailed case study derived from industrial data is used to illustrate the potential of the proposed approach.     

A resource portfolio planning model using sampling-based stochastic programming and genetic algorithm

Resource portfolio planning optimization is crucial to high-tech manufacturing industries. One of the most important characteristics of such a problem is intensive investment and risk in demands. In this study, a nonlinear stochastic optimization model is developed to maximize the expected profit under demand uncertainty. For solution efficiency, a stochastic programming-based genetic algorithm (SPGA) is proposed to determine a profitable capacity planning and task allocation plan. The algorithm improves a conventional two-stage stochastic programming by integrating a genetic algorithm into a stochastic sampling procedure to solve this large-scale nonlinear stochastic optimization on a real-time basis. Finally, the tradeoff between profits and risks is evaluated under different settings of algorithmic and hedging parameters. Experimental results have shown that the proposed algorithm can solve the problem efficiently.     

Improving the non-dominated sorting genetic algorithm using a gene-therapy method for multi-objective optimization

The non-dominate sorting genetic algorithmic-II (NSGA-II) is an effective algorithm for finding Pareto-optimal front for multi-objective optimization problems. To further enhance the advantage of the NSGA-II, this study proposes an evaluative-NSGA-II (E-NSGA-II) in which a novel gene-therapy method incorporates into the crossover operation to retain superior schema patterns in evolutionary population and enhance its solution capability. The merit of each select gene in a crossover chromosome is estimated by exchanging the therapeutic genes in both mating chromosomes and observing their fitness differentiation. Hence, the evaluative crossover operation can generate effective genomes based on the gene merit without explicitly analyzing the solution space. Experiments for nine unconstrained multi-objective benchmarks and four constrained problems show that E-NSGA-II can find Pareto-optimal solutions in all test cases with better convergence and diversity qualities than several existing algorithms.     

An improved monotone algorithm for scheduling related machines with precedence constraints

We answer an open question posed by Krumke et al. (2008) [6] by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an O(logm)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from Krumke et al. [6] and Thielen and Krumke (2008) [8], which have an approximation guarantee of O(m^2/3).     

Evolutionary hybrid approaches for generation scheduling in power systems

Generation scheduling (GS) in power systems is a tough optimisation problem which continues to present a challenge for efficient solution techniques. The solution is to define on/off decisions and generation levels for each electricity generator of a power system for each scheduling interval. The solution procedure requires simultaneous consideration of binary decision and continuous variables. In recent years researchers have focused much attention on developing new hybrid approaches using evolutionary and traditional exact methods for this type of mixed-integer problems. This paper investigates how the optimum or near optimum solution for the GS problem may be quickly identified. A design is proposed which uses a variety of metaheuristic, heuristics and mathematical programming techniques within a hybrid framework. The results obtained for two case studies are promising and show that the hybrid approach offers an effective alternative for solving the GS problems within a realistic timeframe.