Solving a multi-objective multi-skilled manpower scheduling model by a fuzzy goal programming approach

Manpower scheduling is an intricate problem in production and service environments with the purpose of generating fair schedules that consider employers’ objectives and employees’ preferences as much as possible. However, sometimes, vagueness of information related to employers’ objectives and employees’ preferences leads to the fuzzy nature of the problem. This paper presents a multi-objective manpower scheduling model regarding the lack of clarity on the target values of employers’ objectives and employees’ preferences. Hence, a fuzzy goal programming model is developed for the presented model. Afterwards, two fuzzy solution approaches are used to convert the fuzzy goal programming model to two single-objective models. Finally, the results obtained by both single-objective models are compared with each other to select the solution that has the greatest degree of the satisfaction level of employers’ objectives and employees’ preferences.     

A disjunctive graph model and framework for constructing new train schedules

Train scheduling is a complex and time consuming task of vital importance in many countries. To create completely new train schedules that are more accurate and efficient than permitted by current techniques, a novel “hybrid” job shop approach is proposed and implemented in this paper. Unique characteristics of train scheduling are firstly incorporated into a disjunctive graph representation of the solution. Dedicated “stand-alone” constructive algorithms that utilise this representation are then developed. The modelling approach and the constructive algorithms are essential as they provide the basis for which meta-heuristics and other iterative refinement algorithms can be applied. A numerical investigation and case study is provided and demonstrates the viability of the modelling approach. Furthermore it is demonstrated that good quality solutions are provided with reasonable computational effort.     

An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls

This paper presents a preference-based method to handle optimization problems with multiple objectives. With an increase in the number of objectives the computational cost in solving a multi-objective optimization problem rises exponentially, and it becomes increasingly difficult for evolutionary multi-objective techniques to produce the entire Pareto-optimal front. In this paper, an evolutionary multi-objective procedure is combined with preference information from the decision maker during the intermediate stages of the algorithm leading to the most preferred point. The proposed approach is different from the existing approaches, as it tries to find the most preferred point with a limited budget of decision maker calls. In this paper, we incorporate the idea into a progressively interactive technique based on polyhedral cones. The idea is also tested on another progressively interactive approach based on value functions. Results are provided on two to five-objective unconstrained as well as constrained test problems.     

A fuzzy goal programming approach to multi-objective optimization problem with priorities

In goal programming problem, the general equilibrium and optimization are often two conflicting factors. This paper proposes a generalized varying-domain optimization method for fuzzy goal programming (FGP) incorporating multiple priorities. According to the three possible styles of the objective function, the varying-domain optimization method and its generalization are proposed. This method can generate the results consistent with the decision-maker (DM)’s expectation, that the goal with higher priority may have higher level of satisfaction. Using this new method, it is a simple process to balance between the equilibrium and optimization, and the result is the consequence of a synthetic decision between them. In contrast to the previous method, the proposed method can make that the higher priority achieving the higher satisfactory degree. To get the global solution of the nonlinear nonconvex programming problem resulting from the original problem and the varying-domain optimization method, the co-evolutionary genetic algorithms (GAs), called GENOCOPIII, is used instead of the SQP method. In this way the DM can get the optimum of the optimization problem. We demonstrate the power of this proposed method by illustrative examples.     

A Lagrangian heuristic algorithm for a real-world train timetabling problem

The train timetabling problem (TTP) aims at determining an optimal timetable for a set of trains which does not violate track capacities and satisfies some operational constraints.In this paper, we describe the design of a train timetabling system that takes into account several additional constraints that arise in real-world applications. In particular, we address the following issues:

•

Manual block signaling for managing a train on a track segment between two consecutive stations.

•

Station capacities, i.e., maximum number of trains that can be present in a station at the same time.

•

Prescribed timetable for a subset of the trains, which is imposed when some of the trains are already scheduled on the railway line and additional trains are to be inserted.

•

Maintenance operations that keep a track segment occupied for a given period.

We show how to incorporate these additional constraints into a mathematical model for a basic version of the problem, and into the resulting Lagrangian heuristic. Computational results on real-world instances from Rete Ferroviaria Italiana (RFI), the Italian railway infrastructure management company, are presented.     

Design of cooperative algorithms for multi-objective optimization: application to the flow-shop scheduling problem

This is a summary of the main results presented in the author’s PhD thesis. This thesis was supervised by El-Ghazali Talbi, and defended on 21 June 2005 at the University of Lille (France). It is written in French and is available at http://www.lifl.fr/~basseur/These.pdf. This work deals with the conception of cooperative methods in order to solve multi-objective combinatorial optimization problems. Many cooperation schemes between exact and/or heuristic methods have been proposed in the literature. We propose a classification of such schemes. We propose a new heuristic called adaptive genetic algorithm (AGA), that is designed for an efficient exploration of the search space. We consider several cooperation schemes between AGA and other methods (exact or heuristic). The performance of these schemes are tested on a bi-objective permutation flow-shop scheduling problem, in order to evaluate the interest of each type of cooperation.     

A hybrid multi-objective artificial bee colony algorithm for burdening optimization of copper strip production

To achieve burdening process optimization of copper strips effectively, a nonlinear constrained multi-objective model is established on the principle of the actual burdening. The problem is formulated with two objectives of minimizing the total cost of raw materials and maximizing the amount of waste material thrown into melting furnace. In this paper, a novel approach called “hybrid multi-objective artificial bee colony” (HMOABC) to solve this model is proposed. The HMOABC algorithm is new swarm intelligence based multi-objective optimization technique inspired by the intelligent foraging behavior of honey bees, summation of normalized objective values and diversified selection (SNOV-DS) and nondominated sorting approach. Two test examples were studied and the performance of HMOABC is evaluated in comparison with other nature inspired techniques which includes nondominated sorting genetic algorithm II (NSGAII) and multi-objective particle swarm optimization (MOPSO). The numerical results demonstrate HMOABC approach is a powerful search and optimization technique for burdening optimization of copper strips.     

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.     

A redundancy detection algorithm for fuzzy stochastic multi-objective linear fractional programming problems

The computational complexity of linear and nonlinear programming problems depends on the number of objective functions and constraints involved and solving a large problem often becomes a difficult task. Redundancy detection and elimination provides a suitable tool for reducing this complexity and simplifying a linear or nonlinear programming problem while maintaining the essential properties of the original system. Although a large number of redundancy detection methods have been proposed to simplify linear and nonlinear stochastic programming problems, very little research has been developed for fuzzy stochastic (FS) fractional programming problems. We propose an algorithm that allows to simultaneously detect both redundant objective function(s) and redundant constraint(s) in FS multi-objective linear fractional programming problems. More precisely, our algorithm reduces the number of linear fuzzy fractional objective functions by transforming them in probabilistic–possibilistic constraints characterized by predetermined confidence levels. We present two numerical examples to demonstrate the applicability of the proposed algorithm and exhibit its efficacy.     

Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization

Due to the vagaries of optimization problems encountered in practice, users resort to different algorithms for solving different optimization problems. In this paper, we suggest and evaluate an optimization procedure which specializes in solving a wide variety of optimization problems. The proposed algorithm is designed as a generic multi-objective, multi-optima optimizer. Care has been taken while designing the algorithm such that it automatically degenerates to efficient algorithms for solving other simpler optimization problems, such as single-objective uni-optimal problems, single-objective multi-optima problems and multi-objective uni-optimal problems. The efficacy of the proposed algorithm in solving various problems is demonstrated on a number of test problems chosen from the literature. Because of its efficiency in handling different types of problems with equal ease, this algorithm should find increasing use in real-world optimization problems.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

Fuzzy project scheduling problem and its hybrid intelligent algorithm

Project scheduling problem is to determine the schedule of allocating resources so as to balance the total cost and the completion time. This paper considers a type of project scheduling problem with fuzzy activity duration times. According to some management goals, three types of fuzzy models are built to solve the project scheduling problem. Moreover, the technique of fuzzy simulation and genetic algorithm are integrated to design a hybrid intelligent algorithm to solve the fuzzy models. Finally, some numerical examples are given to illustrate the effectiveness of the algorithm.     

A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities

This paper presents a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presents a unique solution representation where a food source is represented by two discrete vectors and tabu search (TS) is applied to each food source to generate neighboring food sources for the employed bees, onlooker bees, and scout bees. An efficient initialization scheme is introduced to construct the initial population with a certain level of quality and diversity. A self-adaptive strategy is adopted to enable the DABC algorithm with learning ability for producing neighboring solutions in different promising regions whereas an external Pareto archive set is designed to record the non-dominated solutions found so far. Furthermore, a novel decoding method is also presented to tackle maintenance activities in schedules generated. The proposed DABC algorithm is tested on a set of the well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.     

Using fuzzy set theory in a scheduling problem: A case study

This paper deals with a real scheduling problem where it seems interesting to use fuzzy sets The question of knowing how and when it is possible to use fuzzy sets (rather than probabilities for instance) is discussed in great detail for the studied case. Fuzzy concepts are shown to be very useful and easy to work with in this decision-aid problem.     

A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms

Location of fire stations is an important factor in its fire protection capability. This paper aims to determine the optimal location of fire station facilities. The proposed method is the combination of a fuzzy multi-objective programming and a genetic algorithm. The original fuzzy multiple objectives are appropriately converted to a single unified ‘min–max’ goal, which makes it easy to apply a genetic algorithm for the problem solving. Compared with the existing methods of fire station location our approach has three distinguish features: (1) considering fuzzy nature of a decision maker (DM) in the location optimization model; (2) fully considering the demands for the facilities from the areas with various fire risk categories; (3) being more understandable and practical to DM. The case study was based on the data collected from the Derbyshire fire and rescue service and used to illustrate the application of the method for the optimization of fire station locations.     

A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design

Multi-objective particle swarm optimization (MOPSO) is an optimization technique inspired by bird flocking, which has been steadily gaining attention from the research community because of its high convergence speed. On the other hand, in the face of increasing complexity and dimensionality of today’s application coupled with its tendency of premature convergence due to the high convergence speeds, there is a need to improve the efficiency and effectiveness of MOPSO. In this paper a competitive and cooperative co-evolutionary approach is adapted for multi-objective particle swarm optimization algorithm design, which appears to have considerable potential for solving complex optimization problems by explicitly modeling the co-evolution of competing and cooperating species. The competitive and cooperative co-evolution model helps to produce the reasonable problem decompositions by exploiting any correlation, interdependency between components of the problem. The proposed competitive and cooperative co-evolutionary multi-objective particle swarm optimization algorithm (CCPSO) is validated through comparisons with existing state-of-the-art multi-objective algorithms using established benchmarks and metrics. Simulation results demonstrated that CCPSO shows competitive, if not better, performance as compared to the other algorithms.     

A biobjective optimization model for routing in mobile ad hoc networks

In this paper, the problem of finding optimal paths in mobile ad hoc networks is addressed. More specifically, a novel bicriteria optimization model, which allows the energy consumption and the link stability of mobile nodes to be taken into account simultaneously, is presented. In order to evaluate the validity of the proposed model, a greedy approach is devised. Some preliminary computational experiments have been carried out, in a simulation environment. The numerical results are very encouraging, showing the correctness of the proposed model. Indeed, the selection of a shorter route leads to a more stable route, but to a greater energy consumption. On the other hand, if longer routes are selected the route fragility is increased, but the average energy consumption is reduced.     

A new multi-objective self-organizing optimization algorithm (MOSOA) for spatial optimization problems

Spatial planning is an important and complex activity. It includes land use planning and resource allocation as basic components. An abundance of papers can be found in the literature related to each one of these two aspects separately. On the contrary, a much smaller number of research reports deal with both aspects simultaneously. This paper presents an innovative evolutionary algorithm for treating combined land use planning and resource allocation problems. The new algorithm performs optimization on a cellular automaton domain, applying suitable transition rules on the individual neighbourhoods. The optimization process is multi-objective, based on non-domination criteria and self-organizing. It produces a Pareto front thus offering an advantage to the decision maker, in comparison to methods based on weighted-sum objective functions. Moreover, the present multi-objective self-organizing algorithm (MOSOA) can handle both local and global spatial constraints. A combined land use and water allocation problem is treated, in order to illustrate the cellular automaton optimization approach. Water is allocated after pumping from an aquifer, thus contributing a nonlinearity to the objective function. The problem is bi-objective aiming at (a) the minimization of soil and groundwater pollution and (b) the maximization of economic profit. An ecological and a socioeconomic constraint are imposed: (a) Groundwater levels at selected places are kept above prescribed thresholds. (b) Land use quota is predefined. MOSOA is compared to a standard multi-objective genetic algorithm and is shown to yield better results both with respect to the Pareto front and to the degree of compactness. The latter is a highly desirable feature of a land use pattern. In the land use literature, compactness is part of the objective function or of the constraints. In contrast, the present approach renders compactness as an emergent result.     

Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems

The railway crew scheduling problem consists of generating crew duties to operate trains at minimal cost, while meeting all work regulations and operational requirements. Typically, a railway operation uses tens of thousands of train movements (trips) and requires thousands of crew members to be assigned to these trips. Despite the large size of the problem, crew schedules need to be generated in short time, because large parts of the train schedule are not finalized until few days before operation.