NeuroGenetic approach for combinatorial optimization: an exploratory analysis

Given the NP-Hard nature of many optimization problems, it is often impractical to obtain optimal solutions to large-scale problems in reasonable computing time. For this reason, heuristic and metaheuristic search approaches are used to obtain good solutions fast. However, these techniques often struggle to develop a good balance between local and global search. In this paper we propose a hybrid metaheuristic approach which we call the NeuroGenetic approach to search for good solutions for these large scale optimization problems by at least partially overcoming this challenge. The proposed NeuroGenetic approach combines the Augmented Neural Network (AugNN) and the Genetic Algorithm (GA) search approaches by interleaving the two. We chose these two approaches to hybridize, as they offer complementary advantages and disadvantages; GAs are very good at searching globally, while AugNNs are more proficient at searching locally. The proposed hybrid strategy capitalizes on the strong points of each approach while avoiding their shortcomings. In the paper we discuss the issues associated with the feasibility of hybridizing these two approaches and propose an interleaving algorithm. We also provide empirical evidence demonstrating the effectiveness of the proposed approach.     

Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems

In this paper, we propose a generic approach to find compromise solutions for multiple-objective scheduling problems using metaheuristics. As an illustration, we present a new hybrid tabu search/variable neighbourhood search application of this approach for the solution of a bi-objective scheduling problem. Through numerical experiments we demonstrate its efficiency and effectiveness. We have confirmed that compromise programming with the tabu-VNS metaheuristic generates solutions that approach those of the known reference sets.     

A Neural Network Application in Personnel Scheduling

In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems.     

A tabu search algorithm for scheduling pharmaceutical packaging operations

This paper addresses a practical scheduling problem arising in the packaging department of a pharmaceutical industrial plant. The problem is modeled as a multi-purpose machine scheduling problem with setup and removal times, release and due dates and additional constraints related to the scarce availability of tools and human operators. The objective functions are minimization of makespan and maximum tardiness in lexicographic order. Representing a solution with a directed graph allows us to devise an effective tabu search algorithm to solve the problem. Computational experiments, carried on real and randomly generated instances, show the effectiveness of this approach.     

A “Logic-Constrained” Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite

The daily photograph scheduling problem of earth observation satellites such as Spot 5 consists of scheduling a subset of mono or stereo photographs from a given set of candidates to different cameras. The scheduling must maximize a profit function while satisfying a large number of constraints. In this paper, we first present a formulation of the problem as a generalized version of the well-known knapsack model, which includes large numbers of binary and ternary logical constraints. We then develop a tabu search algorithm which integrates some important features including an efficient neighborhood, a dynamic tabu tenure mechanism, techniques for constraint handling, intensification and diversification. Extensive experiments on a set of large and realistic benchmark instances show the effectiveness of this approach.     

Scheduling project networks with resource constraints and time windows

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems.The treatment is done by a structural approach that involves a generalization of both the disjunctive graph method in job shop scheduling [1] and the order theoretic methods for precedence constrained scheduling [18,23,24]. Besides theoretical insights into the problem structure, this approach also leads to rather powerful branch-and-bound algorithms. Computational experience with this algorithm is reported.     

Efficient multi-objective tabu search for emergency equipment maintenance scheduling in disaster rescue

The paper describes a mathematical model of the emergency equipment maintenance scheduling problem particularly in disaster rescue operations, which aims to achieve a good balance between operational capability achieved by maintenance, cost-effectiveness, maintenance risks, and reserved maintenance capability for sustainable operations. We design a compact solution encoding that greatly facilitates the search process, and develop an efficient multi-objective tabu search algorithm that evolves a set of solutions towards the Pareto optimal frontier, using a weighted function based on the decision-maker’s preference to guide the search procedures. Simulation experiments and real-world application results demonstrate the effectiveness of our approach.     

A composite algorithm for multiprocessor scheduling

A composite algorithm is developed for the classical problem of scheduling independent jobs on identical parallel machines with the objective of minimizing the makespan. The algorithm at first obtains a family of initial partial solutions and combines these partial solutions until a feasible solution is generated. Then local search procedures are used for improving the solution. The effectiveness of this approach is evaluated through extensive computational comparisons with recent improvement heuristics for different classes of benchmark instances.     

Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions. When does an optimal schedule exist (provided that there are feasible schedules)? When does it have a finite/polynomial number of interruptions? Do they occur at integral/rational points only? These theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer some of these basic questions for a rather general scheduling model (including, as the special cases, the classicalmodels such as parallelmachine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of the objective functions including nearly all known. For some two special cases of objective functions (including, however, all classical ones), we prove the existence of an optimal solution with a special “rational structure.” An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

A market approach to decentralized control of a manufacturing cell

Based on a fictitious market model, a decentralized approach is presented for the workstation scheduling in a CNC workshop. A multi-agent framework is proposed, where job agents and resource agents act as buyers and sellers of resource in the virtual market. With cost and benefit calculation of these agent activities, which reflects the state of the production environment, various, and often conflicting goals and interests influencing the scheduling process in practice can be balanced through a unified instrument offered by the markets. The paper first introduces a heuristic procedure that makes scheduling reservations in a periodic manner. A multi-agent framework is then introduced, in which job agents and resource agents seek appropriate job–workstation matches through bidding in the construction of the above periodic “micro-schedules”. A pricing policy is proposed for the price-directed coordination of agent activities in this. Simulation results demonstrate the feasibility of the proposed approach and give some insights on the effects of some decision making parameters. Future work will be focused on the designing of some more sophisticated coordination mechanism and its deployment.     

A general approach for optimizing regular criteria in the job-shop scheduling problem

Even though a very large number of solution methods has been developed for the job-shop scheduling problem, a majority has been designed for the makespan criterion. In this paper, we propose a general approach for optimizing any regular criterion in the job-shop scheduling problem. The approach is a local search method that uses a disjunctive graph model and neighborhoods generated by swapping critical arcs. The connectivity property of the neighborhood structure is proved and a novel efficient method for evaluating moves is presented. Besides its generality, another prominent advantage of the proposed approach is its simple implementation that only requires to tune the range of one parameter. Extensive computational experiments carried out on various criteria (makespan, total weighted flow time, total weighted tardiness, weighted sum of tardy jobs, maximum tardiness) show the efficiency of the proposed approach. Best results were obtained for some problem instances taken from the literature.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

Metaheuristics for scheduling jobs with incompatible families on parallel batching machines

In this paper, we discuss the scheduling of jobs with incompatible families on parallel batching machines. The performance measure is total weighted tardiness. This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication where the machines can be modelled as parallel batch processors. Given that this scheduling problem is NP-hard, we suggest an ant colony optimization (ACO) and a variable neighbourhood search (VNS) approach. Both metaheuristics are hybridized with a decomposition heuristic and a local search scheme. We compare the performance of the two algorithms with that of a genetic algorithm (GA) based on extensive computational experiments. The VNS approach outperforms the ACO and GA approach with respect to time and solution quality.     

A three-machine permutation flow-shop problem with minimum makespan on the second machine

In this paper, we consider a three-machine permutation flow-shop scheduling problem where the criterion is to minimize the total completion time without idle times subject to the minimum makespan on the second machine. This problem is NP-hard while each of the objective functions alone can be optimized in polynomial time. We develop a branch-and-bound algorithm with effective branching rules and dominance properties which help to reduce the search space. By our computational experiments, the branch-and-bound algorithm is comparable to a recent mixed integer programming solver and, for some kinds of problem instances, the branch-and-bound algorithm outperforms the solver. On the other hand, the computational result would indicate that the hierarchical scheduling problems are essentially hard in both theoretical and computational points of view.     

Planning horizons for multi-item hierarchical production scheduling problems: A heuristic search procedure

A proper planning horizon is important to the effectiveness of planning results. However, there is no planning horizon study dealing with multi-item, multi-level production planning problems which are often encountered in reality. In this study, we develop a direct search procedure for finding planning horizons for a multi-item hierarchical production planning process which consists of an aggregate planning problem and a master production scheduling problem. Experimental results show that the search heuristic is quite efficient in finding planning horizons for both aggregate planning problem and the master scheduling problem. The results also show that the master schedule planning horizons need not be longer than the aggregate planning horizons.     

Parallel machine scheduling with common due windows

With the prevalence of on-time scheduling, timely product submission has become a crucial contributor to customer satisfaction. Studies examining on-time scheduling primarily seek to determine the minimum weighted sum of earliness and tardiness penalties. This study assumes that all machines are identical. Furthermore, this study assumes that jobs are independent and share a common due date window when investigating scheduling problems involving parallel machines with a minimum total number of early and tardy jobs (or maximum number of on-time jobs). This study presents related theorems and a novel simplified algorithm based on the problem. Additionally, rule characteristics are examined, and simulated data are used to verify the effectiveness and timeliness of the proposed algorithm. The theoretical proof and data test results all indicate that the proposed approach obtains the best solution within the shortest time.     

Scheduling of multistage fast-moving consumer goods plants

Fast-moving consumer goods (FMCG) plants are required to be highly flexible due to their multiproduct nature and frequent portfolio changes with seasons or consumer preferences. The multipurpose nature of equipment units usually results in changeover activities which can increase the production scheduling model’s size significantly. The objective of this paper is to present two approaches to decrease the number of changeover activities. The first approach aims to reduce unit flexibility by reducing the allowable task to unit allocations. The second approach emphasises sequencing operations on units. By limiting the set of possible task sequences in the scheduling problem, the number of allowable activities (especially changeovers) is decreased and the optimisation procedure has a smaller search space. The results of these approaches, tested against realistically sized instances indicate their effectiveness in reducing the model size and the solution time, enabling the solution of industrial examples which previously could not be solved.     

A tabu search approach for the single machine mean tardiness problem

In this paper, a tabu search approach is proposed for solving the single machine mean tardiness scheduling problem. Simulation experiment results obtained from the tabu search approach and three other heuristics are compared. Although computation time is increased, the results indicate that the proposed approach provides a much better solution than the other three approaches.     

Modeling, simulation and optimization in logistics

This text summarizes the PhD thesis defended by the author in March 2009 under the supervision of Pasquale Legato at the University of Calabria, Italy. The thesis is written in English and is available for download at the following URL: . It aims to explore friendly Operations Research tools for modeling and simulation of logistics processes, with particular interest for mathematical programming models combined with stochastic simulation tools. In particular key assignment and scheduling problems that arise in maritime container terminals are explored. Initially it is presented a study on different modeling paradigms devoted to the representation of logistical processes and the formalization of problems with complex scheduling/assignment constraints. Successively an IP model for managing the assignment of a pool of rail-mounted gantry cranes to berthed vessels is proposed. Then, according to a functional integration approach, a second model centered on the intra-ship scheduling of vessel container bulks to the assigned cranes is further formulated. Finally a simulation-based optimization approach is investigated and the effectiveness of recent search methods is evaluated by comparison with a commercial solver.