Abstract: The fitting of curves in computer aided geometric design is generally regarded as an optimisation problem. According to the application, conditions to be satisfied can make the problem difficult to solve with classical methods. Stochastic ones, such as genetic algorithms, therefore appear as a relevant way of solving. We consider here a curve fitting problem aiming the generation of shapes with specific curvature variations. A particular curve model have been developed with this aim. Its implementation within a genetic algorithm have been carried out. We describe its main characteristics and present promising result. This technique can be used as an alternative method in the design of car bodies.
Abstract: A new metaheuristic for (combinatorial) optimisation is presented: memetic algorithms with population management or MA$|$PM. A MA$|$PM is a memetic algorithm, that combines local search and crossover operators, but its main distinguishing feature is the use of distance measures for population management. Population management strategies can be developed to dynamically control the diversity of a small population of high-quality individuals, thereby avoiding slow or premature convergence and achieve excellent performance on hard combinatorial optimisation problems. The new algorithm is tested on two problems: the multidimensional knapsack problem and the weighted tardiness single machine scheduling problem. On both problems, population management is shown to be able to improve the performance of a similar memetic algorithm without population management.
Abstract: The Capacitated Arc Routing Problem (CARP) is a very hard vehicle routing problem for which the objective –- in its classical form –- is the minimisation of the total cost of the routes. In addition, one can seek to minimize also the cost of the longest trip. In this paper, a multi-objective genetic algorithm is presented for this more realistic CARP. Inspired by the second version of the Non-dominated Sorted Genetic Algorithm framework, the procedure is improved by using good constructive heuristics to seed the initial population and by including a local search procedure. The new framework and its different flavour is appraised on three sets of classical CARP instances comprising 81 files. Yet designed for a bi-objective problem, the best versions are competitive with state-of-the-art metaheuristics for the single objective CARP, both in terms of solution quality and computational efficiency: indeed, they retrieve a majority of proven optima and improve two best-known solutions.
Abstract: To offer high quality services, when users are increasingly demanding and competition more and more hard, is now a major problem that transportation companies are faced with. So, ensuring a regular traffic needs to identify the randomly occurring disturbances that affect the transportation system and to eliminate or reduce their impacts on the traffic. This paper presents a decision support system TRSS (Traffic Regulation Support System). TRSS is a supervision environment for the regulation of urban transportation system. TRSS (tram and bus) is based on the regulation operator decision-making process. It provides the operator with the information he needs to identify disturbances and evaluate potential corrective actions to be carried out, according to the regulation strategy he has selected. The first part of the paper presents the decision model we work with. The second part deals with the functional model used in the decision support system. Decision support system for transportation and characteristics of a DSS for a transportation system are described in the third part. In the fourth part, we present the components of the decision-making TRSS supervision tool. In the fifth part, we present the criteria of evaluation and the sixth part is devoted to the presentation of the results.
Abstract: This paper considers the problem of scheduling $n$ jobs on a single machine to minimize the number of tardy (or late) jobs. Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Using new and efficient lower bounds and several dominance rules, a branch and bound scheme is proposed based on the definition of a master sequence, i.e. a sequence containing at least one optimal sequence. With this procedure, 95% of 140-job instances are optimally solved in a maximum of one-hour CPU time.
Abstract: Computing a schedule for a given single machine problem is often difficult for irregular criteria, but when the data are uncertain, the problem is much more complicated. In this paper, we modify a genetic algorithm to compute robust schedules when release dates are subject to small variations. Two types of robustness are distinguished: quality robustness or robustness in the objective function space and solution robustness or robustness in the solution space. The modified genetic algorithm is applied to a just-in-time scheduling problem, a common problem in several industries.
Abstract: This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed-integer linear programming. By relaxing some constraints, it is possible to propose a Lagrangean relaxation algorithm which gives both a lower and upper bound. Although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs, and some computational results are presented.
Abstract: The general one-machine scheduling problem is strongly $\mathcalNP$-Hard when the objective is to minimize the weighted number of late jobs. Few methods exist to solve this problem. In an other paper, we developed a Lagrangean relaxation algorithm which gives good results on many instances. However, there is still room for improvement, and a metaheuristic might lead to better results. In this paper, we decided to use a Genetic Algorithm (GA). Although a GA is somewhat easy to implement, many variations exist, and we tested some of them to design the best GA for our problem. Three different engines to evaluate the fitness of a chromosome are considered, together with four types of crossover operators and three types of mutation operators. An improved GA is also proposed by applying local search on solutions determined from the chromosome by the engine. Numerical experiments on different tests of instances are reported. They show that starting from an initial population already containing a good solution is very effective.
Abstract: This paper focuses on the problematic of the complex system maintenance in a cooperative environment composed of several decision centers, taking into account communication times. Maintenance activities generate a specific issue for the scheduling of tasks since they lead to identify dynamically new tasks or to modify the duration of planned tasks. In addition, when an unexpected event is detected by a decision center, some modifications of the schedule desired by this decision center may have consequences on tasks under the control of other decision centers. In fact, there exist some constraints between the jobs under the control of different decision centers. Each modification of the execution of a job should be submitted to the approval of each concerned decision center. It implies a communication time between all these decision centers. Nevertheless, these communication times could be not compatible with desired modifications. This is why we present an algorithm to ensure re-scheduling feasibility, including communication times between decision centers for the maintenance of complex systems in coordinated environment. Finally, we implement our algorithm on the industrial context of the TGV maintenance in the French railway company.
Abstract: The goal of this paper is to solve a continuous time production planning problem, where production rates are supposed to be piecewise constant. The problem is then to determine not only the rates, but also the times, called switching times, at which these rates may change. An iterative procedure is proposed where, at the first step, optimal rates are determined given the switching times and, at the second step, new switching times are added given the rates. Various models are proposed and discussed for the first step, and a linear programming formulation is finally retained. A special effort has been made to reduce the size of the linear programming problem solved at each iteration of the procedure. Several rules to remove or add switching times are also analyzed. Computational experiments are presented comparing two versions of the procedure and showing its efficiency.
Abstract: The school bus routing problem discussed in this paper, is similar to the standard vehicle routing problem, but has several interesting additional features. In our school bus routing problem, we assume that a set of potential stops is given, as well as a set of students that can walk to one or more stops.
Abstract: In this study, we wish to help a decision maker in designing an electronic component at a minimium cost. After modeling the problem, we have a scheduling problem where a set of tasks with precedence constraints, release dates and due dates has to be scheduled on different resources. The objective is to minimize the cost of the resources used for sequencing all tasks on time.
Abstract: Robustness is a very important concept present in diverse areas related to MCDM. In general words we can say that robustness is an attribute related to the “ability of a subject to cope well with uncertainties”, more precisely the uncertainties that accompany the input of a system. In this work we are particularly interested in the concept of robust solution in optimisation and its application to find the final set of alternatives in Multiple-Objective problems (MOP). The application of robustness described here is framed in a specific “Released when Completing blocking” (RCb) bi-objective hybrid flowshop scheduling problem, but the methodologies studied can be adapted to other classes of problems.
Abstract: The school bus routing problem discussed in this paper, is similar to the standard vehicle routing problem, but has several interesting additional features. In the standard VRP all stops to visit are given. In our school bus routing problem, we assume that a set of \emphpotential stops is given, as well as a set of students that can walk to one or more of these potential stops. The school buses used to pick up the students and transport them to their schools have a finite capacity. The goal of this routing problem is to select a subset of stops that will actually be visited by the buses, determine which stop each student should walk to and develop a set of tours that minimize the total distance travelled by all buses. We develop an integer programming formulation for this problem, as well as a problem instance generator. We then show how the problem can be solved using a commercial integer programming solver and discuss some of our results on small instances.
Abstract: Several new metaheuristic optimization approaches use a distance measure in the solution space to control diversity. Memetic algorithms with population management (MA|PM) are relatively new metaheuristics, that actively control the diversity of a small population of high-quality solutions. The distance measure used should reflect the difference between a given pair of solutions in the solution space. Although difficult to prove, it seems natural to conjecture that a distance measure that more accurately reflects the distance between two solutions is preferable to one that does not. For permutation problems, a myriad of distance measures has been developed, originating in different domains (statistics, computer science, molecular biology,...). In this paper, we look at nine of them. We determine the effort required to calculate them and develop a normalized version of each distance measure, that produces a value between 0 and 1. We then compare their performance by implementing them in a simple MA|PM for the single-machine total weighted tardiness scheduling problem.
Abstract: The Capacitated Arc Routing Problem or CARP is raised for instance by urban refuse collection. The paper shows how to modify an efficient memetic algorithm for the CARP to tackle two other problems: a CARP with stochastic demands and a bi-objective CARP in which the second objective is the cost of the longest trip or makespan. The two new algorithms are finally combined for the bi-objective case with stochastic demands. The resulting MOGA uses average demands to compute a priori a set of non-dominated solutions that will resist random demand fluctuations on the field. Under mild simplifying assumptions, mathematical expressions are derived for the two objectives (expected total cost and expected makespan), thus avoiding simulation or noising techniques to evaluate chromosomes. The algorithm is evaluated on classical CARP instances, modified to have random demands. The non-dominated solutions obtained are very robust, with null standard deviations in most cases. A simulation phase is performed a posteriori to evaluate the behavior of solutions on the field. It confirms the expected values computed by the MOGA, the accuracy of mathematical expressions and the validity of assumptions. The general method presented could be applied to other combinatorial optimization problems.
Abstract: In this paper we describe the development of libOR, an on-line library for the operations research (OR) community. The design and operation of this website is inspired by the Open Source movement and recent developments such as Wikipedia. In operations research, data sets are exchanged between researchers in order to test the performance of newly developed algorithms. Currently, the exchange of these data sets suffers from many problems. One of the main problems is that data sets are currently exchanged through a centrally maintained website, which makes it slow to respond to new developments. By applying an Open Source approach to content creation, we hope to spur the diffusion of information within the operations research community.
Abstract: We developed a genetic algorithm and a constraint programming based branch-and-bound algorithm to solve multiprocessor task scheduling problem in hybrid flow-shop environments. We then combined these two approaches to benefit from their different aspects. Computational experiments are conducted on a large set of instances and the resulting memetic algorithm gives the best results so far.
Abstract: A new metaheuristic for (combinatorial) optimisation is presented: memetic algorithms with population management or MA$|$PM. A MA$|$PM is a memetic algorithm, that combines local search and crossover operators, but its main distinguishing feature is the use of distance measures for \emphpopulation management. Population management \emphstrategies can be developed to dynamically control the diversity of a small population of high-quality individuals, thereby avoiding slow or premature convergence and achieve excellent performance on hard combinatorial optimisation problems.
Abstract: libOR can be described as a comprehensive database of OR problem data sets, similar to the OR library. Although libOR consists of a central database, it is decentrally updateable. Unlike other similar databases, libOR also contains a database of results. libOR uses XML technology to validate data sets. libOR has a number of responsibles that make sure that the problems and results are up to date, it largely depends on the co-operation of the research community.
Abstract: This paper presents a new technique for finding robust and flexible vehicle routing solutions in practical situations, combining the optimisation power of metaheuristics with a sampling-based approach to evaluating the robustness and flexibility of a solution. This approach overcomes the main limitations of most current methods. Using experiments, we show that the method is versatile and capable of handling practical real-life stochastic optimisation problems.
Abstract: In this paper, we apply the framework of genetic algorithms with population management (GA$|$PM) to the capacitated arc routing problem (CARP). GA$|$PM use distance measures to control the diversity of a small population of high-quality solutions. The algorithm is compared on the 23 GDB instances from Golden, DeArmon and Baker. The GA$|$PM is able to retrieve the same solutions much faster than an improved memetic algorithm, and can therefore be considered the best method to date.
Abstract: We developed a genetic algorithm and a constraint programming based branch-and-bound algorithm to solve multiprocessor task scheduling problem in hybrid flow-shop environments. We then combined these two approaches to benefit from their different aspects. We will present our computational results which are very encouraging.
Abstract: This paper addresses resolution of a robust scheduling problem arising at the French railways company. The objective is to reduce the immobilization of trains during the maintenance operations. The processing times of operations are submitted to hazards and the objective is to minimize both the total completion time (\emphi.e. the makespan) and to limit the random event consequences on solution quality. Solutions must be robust when facing some variations of processing times. Due to periodic modifications in the composition of trains a computer aided design system is required to avoid periodic manual planning computation. This system must provide machine sequence of operations, makespan evaluation and an evaluation of the processing time variation consequences. The purpose of this paper is to present a dedicated genetic algorithm fo robust solutions computation.
Abstract: The Capacitated Arc Routing Problem (CARP) is a very hard vehicle routing problem raised for instance by urban waste collection. In addition to the total route length (the only criterion minimized in the academic problem), waste management companies seek to minimize also the length of the longest trip. In this paper, a bi-objective genetic algorithm is presented for this more realistic CARP, never studied before in literature. Based on the NSGA-II template, it includes two-key features: use of good constructive heuristics to seed the initial population and hybridization with a powerful local search procedure. This genetic algorithm is appraised on 23 classical CARP instances, with excellent results. For instance, for a majority of instances, its efficient solutions include an optimal solution to the academic CARP (minimization of the total route length).
Abstract: The fitting of curves in computer aided geometric design is generally regarded as an optimisation problem. According to the application, conditions to be satisfied can make the problem difficult to solve with classical methods. Stochastic ones, such as genetic algorithms, therefore appear as a relevant way of solving. We consider here a curve fitting problem aiming the generation of shapes with specific curvature variations. A particular curve model have been developed with this aim. Its implementation within a genetic algorithm have been carried out. We describe its main characteristics and present a first result.
Abstract: Classical genetic algorithms (GA)-pioneered by among others Holland (1975) and Goldberg (1989) have been shown experimentally to perform rather poorly on many combinatorial problems. Large memory requirements, large running times and poor performance in terms of solution quality characterise many GA implementations. In this paper we present a new type of genetic algorithm that attempts to overcome some of the drawbacks of classical genetic algorithms. This is done by measuring and controlling the diversity of a small population of high-quality individuals. The new GA is called GA$|$PM, genetic algorithm with population management.
Abstract: Distributed re-scheduling Processes are involved in many industrial cases (multi-site problems, multi-entities problems) and represent a large part of decision systems literature. The emerging problems lie on both, re-scheduling process and structure of decision systems. The literature shows the influence of some parameters of the decision cooperative process on the re-scheduling process, when the objective is the minimization of the makespan. This paper proposes a cooperation multi-entities process to obtain information in terms of induced time. The proposed model is based on colored temporized Petri nets, in which weights on arcs are dynamically calculated according to the results of the re-scheduling algorithm and to the objectives of local entities of the decision process.
Abstract: Computing a schedule for a given single machine problem is often difficult for irregular criteria, but when the data are uncertain, the problem is much more complicated. In this paper, we create a genetic algorithm to compute robust scedules when release dates are subject ot small variations. Instead of evaluating a single fitness function, at each iteration, several functions are evaluated taking into account the variation of the data. This methods leads to robust solutions, meaning that the value of the objective function remains high when small variations in some release dates occurs.
Abstract: The Capacitated Arc Routing Problem (CARP) is a very hard vehicle routing problem raised for instance by urban waste collection. In addition to the total route length (the only criterion minimized in the academic problem), waste management companies seek to minimize also the length of the longest trip. A bi-objective genetic algorithm is presented for this more realistic CARP, never studied before in literature. Based on the NSGA-II template, it includes two-key features: use of good constructive heuristics to seed the initial population and hybridization with a powerful local search procedure. This genetic algorithm is appraised on 23 classical CARP instances, with excellent results.
Abstract: The general one machine total weighted tardiness problem is one of the most difficult scheduling problem. In the general case only few results exists. The problem can be described as follows: a set of $n$ jobs has to be sequenced on a single machine. Preemption is not allowed and only one job can be processed at the same time. Each job cannot start before its release date $r_j$, is processed during $p_j$ time units and should be completed before its due date $d_j$. A weight $w_j$ is associated to each job. The tardiness of a job $j$ is defined by $\max(0, C_j-d_j)$, where $C_j$ is the completion time of the job. The objective is to minimize the total weighted tardiness, $\sum w_jT_j$. When a solution is represented by a permutation of the jobs, it is easy to build a genetic algorithm procedure and apply usual crossover and mutation operators. A new metaheuristics, scatter search, can use the same type of representation (permutation). A comparative study between the two approaches is conducted on this one machine scheduling problem. The general behavior of the two methods differs. The study will point out these differences.
Abstract: This paper presents a Lagrangean relaxation approach for solving a parallel machine scheduling problem where the objective is to minimize the weithed number of late jobs. This approach is an extension of an approach that has been successfully applied on the one-machine case.
Abstract: The problem of minimizing the weighted number of late jobs subject to release date on parallel machines is $\mathcalNP$-Hard. An innovative data structure is presented and used for a simple efficient heuristic. Numerical results are presented. Based on this first solution a tabu search procedure is developped and improves again the results. Compare to another approach, our method gives competitive results up to 60 jobs on 6 machines.
Abstract: In this paper, the problem consist in minimizing the weighted number of late jobs on parallel machine. Several heuristics and metaheuristics using a common neighborhood are presented and evaluated. Best results are given by an improved tabu search procedure with cycle detection and dynamic tenure adaptation.
Abstract: The problem of minimizing the weighted number of late jobs subject to release date on a single machine is strongly $\mathcalNP$-Hard. Few methods exist to solve this problem. In an other paper, we have developed a Lagrangean relaxation algorithm which give good results over many instances. In some cases, a meta-heuristic could lead to better results and we decided to use a Genetic Algorithm (GA). Even if a GA is somewhat easy to implement, many variations exist. In this paper, we try some of them and report the results. When using GA, the most familiar representation of the chromosomes for scheduling problem is the permutation of the jobs. Three different engines are used to evaluate the fitness of a chromosome. Moreover, four types of crossover operators and three mutation operators have been tested. The goal of this paper is to find the best association of these parameters and use it to improve the solution given by the Lagrangean relaxation. A combination of all parameters is tested on a set of 1000 100-job problems. Computational results are reported and the GA with the best combination is tested on other problems.
Abstract: The problem of minimizing the weighted number of late jobs subject to release date on a single machine is strongly $\mathcalNP$-Hard. In an other paper, we have developped a Lagrangean relaxation algorithm to solve the problem. A meta-heuristic could lead to better results and we decided to use a Genetic Algorithm (GA). Even if a GA is somewhat easy to implement, many variations exist. In this paper, we try some of them and report the results. When using GA, the most familiar representation of the chromosoms for scheduling problem is the permutation of the jobs. Three different engines are used to evaluate the fitness of a chromosom. Moreover, four types of crossover operators and three mutation operators have been tested. Some computational results are reported.
Abstract: This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed-integer linear programming. By relaxing some constraints, it is possible to propose a Lagrangean relaxation algorithm which gives both a lower and upper bound. Although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs, and some computational results are presented.
Abstract: In some industries, it is preferable to use control policies to schedule production. Starting from any configuration of the stocks, an optimal control policy leads the surplus level to a stationary state. The goal of this paper is to provide some control policies for a continuous-time production scheduling problem where demand is constant. For a one machine and multi-item case, we develop a control policy that we prove to be optimal in a small time interval. We conjecture this policy to be optimal for the whole horizon. This policy is extended for more than one machine and, under some special conditions, this policy is still optimal but also in a small time interval. In the general case, a counter-example is shown.
Abstract: We consider the problem of scheduling $n$ jobs on a single machine where the objective is to minimize the number of late jobs, both in the unweighted and weighted case, and where release dates, processing times and dued dates can be different. A new integer programming formulation is proposed, whose efficiency has been evaluated through Linear Programming (LP) relaxation. However, in large instances (more than 100 jobs), and because the number of variables in the model can be large, the LP relaxation is rather time consuming. Hence, we propose a Lagrangean relaxation in which the relaxed problem can be solved very fast (at most in $O(n^2)$ time) for given multipliers. A subgradient Lagrangean search algorithm is developed, which can solved both the unweighted and weighted case. It is easy to see that, in theory, this algorithm converges to the same lower bound than the one obtained by LP relaxation. As usual in that type of algorithm, the main difficulty lies in the choice of the initial Lagrangean multipliers and their updating. Numerical experiments are presented, which show that instances up to 1000 jobs can be solved, although duality gaps can be large.
Abstract: An original and efficient mixed integer linear programming formulation is proposed, using some properties of the problem. Several cuts can be used to strengthen that formulation and to obtain better bounds by LP relaxation. A branch-and-cut algorithm is derived, whose efficiency will be discussed through some numerical experiments.
Abstract: Models and solution procedures were proposed in a previous work for continuous-time production planning, i.e., when production and demand are expressed in terms of rates instead of quantities. This paper investigates the case where demand is discrete, i.e., corresponds to quantities of products that need to be fulfilled at given points in time. After describing the model and the solution procedure, we show how they can be extended to take discrete demand into account. Numerical experiments on an example are presented and discussed.
Abstract: The paper considers the problem of scheduling $n$ jobs on a single machine to minimize the number of tardy jobs (or late jobs). Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Using new and efficient lower bounds, a branch and bound scheme is proposed based on the definition of a master sequence, i.e., a sequence containing at least an optimal sequence. Numerical experiments are presented.
Abstract: The paper considers the problem of scheduling $n$ jobs on a single machine to minimize the number of tardy jobs (or late jobs). Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Various mixed-integer linear programming formulations are presented and discussed. A new polynomial solvable case is also introduced.
Abstract: In continuous-time planning problems, production is expressed in terms of rates instead of quantities. The objective is to minimize the cost over the whole horizon, and not only at ends of periods like a discrete-time planning problem. We propose a two-level iterative procedure to solve this problem. At the first level, optimal production rates are determined, given the switching times. At the second level, switching times are removed and added, given the production rates. Here, we assume that production rates are piecewise constant. For given switching times, determining the optimal production rates is a non-linear problem. A linear programming model is derived to obtain a solution. At the second level, various rules can be applied to remove and to set switchingtimes. Since the size of the linear programming model depends on the number of switching times, reducing this number at each iteration speeds up the resolution and allows larger problems to be treated. At the second level of the iterative procedure, switching times often do not have to be added for every product. Hence, each product will have its own set of switching times. In the linear programming model, only the necessary variables will be created.
Abstract: In classical production planning problems, the goal is to minimize a cost function over a discrete horizon divided into equal length periods. In continuous-time planning problems, we consider demand and production rates instead of quantities. The objective is then to minimize the cost over the whole horizon. Assuming that the production and demand rates are piecewise constant, we briefly present several models for this problem : Non-Linear, Mixed-Integer-Linear and Linear Programming. In the latter, we study the problem of finding the best switching times, i.e.\/ times at which production rates are allowed to change. Various procedures are discussed, together with some numerical experiments.
Abstract: Computing a schedule for a given single machine problem is often difficult for irregular criteria, but when the data are uncertain, the problem is much more complicated. In this paper, we modify a genetic algorithm to compute robust schedules when release dates are subject to small variations. Two types of robustness are distinguished: quality robustness or robustness in the objective function space and solution robustness or robustness in the solution space. The modified genetic algorithm is applied to a just-in-time scheduling problem, a common problem in several industries.
Abstract: This paper focuses on the problematic of the complex system maintenance in a cooperative environment composed of several decision centers, taking into account communication times. Maintenance activities generate a specific issue for the scheduling of tasks since they lead to identify dynamically new tasks or to modify the duration of planned tasks. In addition, when an unexpected event is detected by a decision center, some modifications of the schedule desired by this decision center may have consequences on tasks under the control of other decision centers. In fact, there exist some constraints between the jobs under the control of different decision centers. Each modification of the execution of a job should be submitted to the approval of each concerned decision center. It implies a communication time between all these decision centers. Nevertheless, these communication times could be not compatible with desired modifications. This is why we present an algorithm to ensure re-scheduling feasibility, including communication times between decision centers for the maintenance of complex systems in coordinated environment. Finally, we implement our algorithm on the industrial context of the TGV maintenance in the French railway company.
Abstract: In scheduling theory, minimizing the weighted number of late jobs in the general case (non-equal release dates) is an objective function usually used as a performance indicator. This paper presents several approaches for the $\mathcalNP$-Hard parallel machine scheduling problem, including two MILP formulations for exact resolution and various heuristics and metaheuristics to solve large size instances. An original data structure is developed and allows flexibility for computing starting times once the sequence is fixed. A simple neighborhood combined with this data structure is used in the heuristics and metaheuristics and give promising results.
Abstract: The general one-machine scheduling problem is strongly $\mathcalNP$-Hard when the objective is to minimize the weighted number of late jobs. Few methods exist to solve this problem. In an other paper, we developed a Lagrangean relaxation algorithm which gives good results on many instances. However, there is still room for improvement, and a metaheuristic might lead to better results. In this paper, we decided to use a Genetic Algorithm (GA). Although a GA is somewhat easy to implement, many variations exist, and we tested some of them to design the best GA for our problem. Three different engines to evaluate the fitness of a chromosome are considered, together with four types of crossover operators and three types of mutation operators. An improved GA is also proposed by applying local search on solutions determined from the chromosome by the engine. Numerical experiments on different tests of instances are reported. They show that starting from an initial population already containing a good solution is very effective.
Abstract: In some industries, it is preferable to use control policies to schedule production. Starting from any configuration of the stocks, an optimal control policy leads the surplus level to a stationary state. The goal of this paper is to provide some control policies for a continuous-time production scheduling problem where demand is constant. For a one machine and multi-item case, we develop a control policy that we prove to be optimal in a small time interval. We conjecture this policy to be optimal for the whole horizon. This policy is extended for more than one machine and, under some special conditions, this policy is still optimal but also in a small time interval. In the general case, a counter-example is shown.
Abstract: This paper considers the problem of scheduling $n$ jobs on a single machine to minimize the number of tardy jobs (or late jobs). Each job has a release date, a processing time and a due date. The general case with non-equal release dates and different due dates is considered. Using new and efficient lower bounds and several dominance rules, a branch and bound scheme is proposed based on the definition of a master sequence, i.e., a sequence containing at least an optimal sequence. With this procedure, 95% of 140-job instances are optimally solved in a maximum of one-hour CPU time.
Abstract: This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed-integer linear programming. By relaxing some constraints, it is possible to propose a Lagrangean relaxation algorithm which gives both a lower and upper bound. Although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs, and some computational results are presented.
Abstract: Metaheuristics are nowadays commonly used for solving combinatorial optimisation problems. Classical genetic algorithms face several problems for convergence and the purpose of the proposed method is to solve efficiently the balance between intensification and diversification during the search. This is done through a careful population management which leads to general improvement of the classical method. As an example, the Capacitated Arc Routing Problem will be solved. The results will be compared to the best existing method (a memetic algorithm). A reminder will be given on all these metaheuristics.
Notes: Invited seminar, The Hong-Kong Polytechnic University, Department of Logistics
Abstract: Today, metaheuristics play an important role in the optimization of difficult problems. Most people have already heard about tabu search or genetic algorithms but don’t know in detail how each of these optimization strategies work. This talk will present some of the metaheuristics used today in many research domains. Two types are introduced: neighborhood metaheuristics and population metaheuristics. The first part presents metaheuristics that handle a single solution at each iteration whereas the latter part presents metaheuristics based on a population of solutions and how this population can be used to find good solutions. A scheduling application is presented at the end and will serve for discussion.
Notes: Invited seminar, University of Antwerp, Faculty of Applied Economic Sciences
Abstract: Metaheuristics play a great role in optimization problem solving. Most of the people have already heard about genetic algorithms but don’t know much about it. This talk will focus on population metaheuristics (i.e. metaheuristics that use a population of solutions instead of a single solution). The presentation will include a description of Genetic Algorithms (GA), Hybrid GA, Memetic Algorithms, Ant Colony Optimization and Scatter Search. A scheduling application will be presented at the end and will serve as a basis for discussion.
Notes: Invited seminar, The Hong-Kong Polytechnic University, Department of Management
Abstract: The Capacitated Arc Routing Problem (CARP) is a very hard vehicle routing problem raised for instance by urban waste collection. In addition to the total route length (the only criterion minimized in the academic problem), waste management companies seek to minimize also the length of the longest trip. A bi-objective genetic algorithm is presented for this more realistic CARP, never studied before in literature. Based on the NSGA-II template, it includes two-key features: use of good constructive heuristics to seed the initial population and hybridization with a powerful local search procedure. Extensions such as $\varepsilon$-dominance and the gender concept are tested and the results were not convincing. Several explanations are provided.
Notes: Invited seminar, University of Valenciennes, French research group on multiple objective mathematical programming
Abstract: Minimizing the number of late jobs on a single machine is a criterion well studied today. Various authors have tackled this problem since 1968 but very few of them have tried to solve it in the general case (problem with differents release dates). Two french teams have recently proposed new properties and efficient procedures for solving this problem. Three exact methods exist today and are competitives. When weights are added in the objective function for each jobs, the problem becomes more complex but can still be efficiently solved for instances up to 100 jobs. The seminar will present a non-exhaustive summary of these approaches.
Abstract: In classical production planning problems, the goal is to minimize a cost function over a discrete horizon divided into equal length periods. In continuous-time planning problems, we consider demand and production rates instead of quantities. The objective is then to minimize the cost over the whole horizon. Assuming that the production and demand rates are piecewise constant, we briefly present several models for this problem : Non-Linear, Mixed-Integer-Linear and Linear Programming. In the latter, we study the problem of finding the best switching times, i.e.\/ times at which production rates are allowed to change. Various procedures are discussed, together with some numerical experiments.
Notes: Invited seminar, Massachusetts Institute of Technology, Cambridge, MA, USA
Abstract: Solving optimisation problems is key to the continuous improvement of productivity in industry. When traditional methods fail, it is natural to consider approximate resolution methods. Metaheuristics, today, play an important role in solving optmisation problems. Over the last few years, these powerful techniques have become necessary tools. The HDR synthesis presents an overview of the classic metaheuristics (descent methods, simulated annealing, tabu search, genetic algorithms), some of the less well-known methods (variable neighbourhood search, GRASP, iterated local search, guided local search, ant colonies) and some advanced techniques (memetic algorithms, scatter search, GA|PM). The intensication and diversification factors of all of these methods were analyzed, as were each methods specific features. The experimentation considered various applications. Based on the analysis and experimentaion, the necessary caracteristics of a good metaheuristic were highlighted and justified.
Abstract: This dissertation presents the study of two optimization problems, one in production planning and the other in scheduling. In industries where items are produced in large quantities, raw material is continuously arriving and final products are continuously leaving the shop-floor. For a medium-term horizon, this process can be considered as continuous, and continuous-time production planning models are more appropriate. A two-step iterative procedure is proposed to solve the problem. In the first step, given the switching times (instants where production rates are allowed to change), optimal production rates are determined by solving a linear programming model, then given the production rates, switching times can be adjusted. Discrete demand and optimal policies in case of constant demand are also developed. In the second part of this dissertation, a general one-machine scheduling problem where the objective is to minimize the number of late jobs is solved. A new polynomially solvable case and many mixed-integer linear programming models are introduced. Linear relaxation of these models gives lower bounds of the problem. Another mixed-integer linear programming model based on a master sequence (sequence containing at least one optimal sequence) is presented. The linear relaxation, after adding new valid inequalities, gives efficient lower bounds. A Lagrangean relaxation is also used and gives a lower and an upper bound. Two branch-and-bound methods are also developed. The branch-and-bound method based on the master sequence solves optimally more than 90% of 140-job instances. Many results are also valid for the problem of minimizing the weighted number of late jobs on a single machine.
