Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

A Common Medium for Programming Operations-Research Models

Operations research is an interdisciplinary science that develops scientific methods for modeling and solving decision-making problems. Arguably, the two most established and commonly practiced OR methodologies are mathematical programming (also called optimization) and discrete-event system simulation (called simulation). Mathematical programming describes a decision problem as decision variables and as mathematical functions of variables that capture the objective and problem constraints. For dynamic systems that are too complex to allow exact, closed-form solutions in continuous time, simulation can identify and describe events of interest and model their occurrences at discrete points in time. Python can glue together independent software environments to improve the software development cycle for sophisticated operations-research applications, which integrate different modeling methodologies.     

Sports scheduling: Problems and applications

Sports scheduling problems mainly consist in determining the date and the venue in which each game of a tournament will be played. Integer programming, constraint programming, metaheuristics, and hybrid methods have been successfully applied to the solution of different variants of this problem. This paper provides an introductory review of fundamental problems in sports scheduling and their formulations, followed by a survey of applications of optimization methods to scheduling problems in professional leagues of different sport disciplines such as football, baseball, basketball, cricket, and hockey. A case study illustrates a real‐life application of integer programming to the schedule of the yearly Brazilian football tournament.     

A distributed and hierarchical strategy for autonomic grid‐enabled cooperative metaheuristics with applications

The adoption of the same cluster‐based programming strategies for grid applications, although requiring minimal effort from a programmer's point of view, does not always take advantage of the available computational resources to their fullest extent. This paper investigates the impact of a distributed and hierarchical autonomic strategy on the performance of parallel metaheuristics to solve hard combinatorial optimization problems on grids. Two problems, the mirrored traveling tournament problem and the bounded diameter minimum spanning tree problem, for which high quality sequential heuristics based on the paradigms of the GRASP and Iterated Local Search metaheuristics already exist, are employed as case‐studies. The computational results obtained on a grid by the novel autonomic strategy show that outstanding performance improvements over the traditional master–worker parallelization approach can be achieved.     

Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms

The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality.     

Improving the Clustering Search heuristic: An application to cartographic labeling

The use of hybrid metaheuristics is a good approach to improve the quality and efficiency of metaheuristics. This paper presents a hybrid method based on Clustering Search (CS). CS seeks to combine metaheuristics and heuristics for local search, intensifying the search on regions of the search space which are considered promising. We propose a more efficient way to detect promising regions, based on the clustering techniques of Density-based spatial clustering of applications with noise (DBSCAN), Label-propagation (LP), and Natural Group Identification (NGI) algorithms. This proposal is called Density Clustering Search (DCS). To analyze this new approach, we propose to solve a combinatorial optimization problem with many practical applications, the Point Feature Cartographic Label Placement (PFCLP). The PFCLP attempts to locate identifiers (labels) of regions on a map without damaging legibility. The computational tests used instances taken from the literature. The results were satisfactory for clusters made with LP and NGI, presenting better results than the classic CS, which indicates these methods are a good alternative for the improvement of this method.     

An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times

This study introduces the problem of minimizing average relative percentage of imbalance (ARPI) with sequence-dependent setup times in a parallel-machine environment. A mathematical model that minimizes ARPI is proposed. Some heuristics, and two metaheuristics, an ant colony optimization algorithm and a genetic algorithm are developed and tested on various random data. The proposed ant colony optimization method outperforms heuristics and genetic algorithm. On the other hand, heuristics using the cumulative processing time obtain better results than heuristics using setup avoidance and a hybrid rule in assignment.     

A study on the use of heuristics to solve a bilevel programming problem

The bilevel programming problem is characterized as an optimization problem that has another optimization problem in its constraints. The leader in the upper level and the follower in the lower level are hierarchically related where the leader's decisions affect both the follower's payoff function and allowable actions, and vice versa. One difficulty that arises in solving bilevel problems is that unless a solution is optimal for the lower level problem, it cannot be feasible for the overall problem. This suggests that approximate methods could not be used for solving the lower level problem, as they do not guarantee that the optimal solution is actually found. However, from the practical point of view near‐optimal solutions are often acceptable, especially when the lower level problem is too costly to be exactly solved thus rendering the use of exact methods impractical. In this paper, we study the impact of using an approximate method in the lower level problem, discussing how near‐optimal solutions on the lower level can affect the upper level objective function values. This study considers a bilevel production‐distribution planning problem that is solved by two intelligent heuristics hierarchically related: ant colony optimization for solving the upper level problem, and differential evolution method to solve the lower level problem.     

Hybrid genetic algorithms for constrained placement problems

When solving real-world problems, often the main task is to find a proper representation for the candidate solutions. Strings of elementary data types with standard genetic operators may tend to create infeasible individuals during the search because of the discrete and often constrained search space. This article introduces a generally applicable representation for 2D combinatorial placement and packing problems. Empirical results are presented for two constrained placement problems, the facility layout problem and the generation of VLSI macro-cell layouts. For multiobjective optimization problems, common approaches often deal with the different objectives in different phases and thus are unable to efficiently solve the global problem. Due to a tree structured genotype representation and hybrid, problem-specific operators, the proposed approach is able to deal with different constraints and objectives in one optimization step     

具有混合动态约束的生产系统优化调度新算法

研究具有混合动态约束的生产系统优化调度问题.在Lagrange松弛法框架下,求解包含混合动态约束的子问题仍然十分复杂,许多算法只能求得子问题的近似解,降低了Lagrange松弛法的有效性.文中提出了一种新的离散状态定义方法,解除了子问题中离散决策变量与连续决策变量的耦合.在此基础上结合动态规划思想,提出了一种新算法,在保证整体最优性的前提下,可以同时对离散和连续状态分别寻优,对算法复杂性进行了初步分析,新算法效率高且可以得到子问题的精确解.电力系统调度问题的数值算例验证了新算法的有效性.     

应用离散事件系统控制理论求解生产调度的新方法

众所周知, 生产调度问题属组合优化问题, 一般来说不存在求得精确最优解的多项式算法. 因此, 对于大规 模调度问题, 人们应用启发式算法和元启发式算法以企求得满意解. 在实际的应用中, 许多工业过程需要满足严格 的工艺约束. 对于这类过程的调度问题, 很难应用启发式算法和元启发式算法, 因为这些方法难于保证所求得调度 的可行性. 为了解决这一问题, 本文以半导体芯片制造中组合设备的调度问题作为例子, 介绍了一种基于离散事件 系统控制理论的生产调度新方法. 利用Petri网建模, 任何违反约束的状态均被描述为非法状态, 而使非法状态出现 的调度则是不可行调度. 通过可行调度的存在性分析, 该方法获得可行解空间并将调度问题转化为连续优化问题, 从而可以有效求解. 并且指出, 该方法可以应用于其他应用领域.     

On concave constraint functions and duality in predominantly black-and-white topology optimization

We study the ‘classical’ discrete, solid-void or black-and-white topology optimization problem, in which minimum compliance is sought, subject to constraints on the available material resource. We assume that this problem is solved using methods that relax the discreteness requirements during intermediate steps, and that the associated programming problems are solved using sequential approximate optimization (SAO) algorithms based on duality. More specifically, we assume that the advantages of the well-known Falk dual are exploited. Such algorithms represent the state-of-the-art in (large-scale) topology optimization when multiple constraints are present; an important example being the method of moving asymptotes (MMA).We depart by noting that the aforementioned SAO algorithms are invariably formulated using strictly convex subproblems. We then numerically illustrate that strictly concave constraint functions, like those present in volumetric penalization, as recently proposed by Bruns and co-workers, may increase the difficulty of the topology optimization problem when strictly convex approximations are used in the SAO algorithm. In turn, volumetric penalization methods are of notable importance, since they seem to hold much promise for generating predominantly solid-void or discrete designs.We then argue that the nonconvex problems we study may in some instances efficiently be solved using dual SAO methods based on nonconvex (strictly concave) approximations which exhibit monotonicity with respect to the design variables.Indeed, for the topology problem resulting from SIMP-like volumetric penalization, we show explicitly that convex approximations are not necessary. Even though the volumetric penalization constraint is strictly concave, the maximum of the resulting dual subproblem still corresponds to the optimum of the original primal approximate subproblem.     

Evolutionary algorithms + domain knowledge = real-world evolutionary computation

We discuss implicit and explicit knowledge representation mechanisms for evolutionary algorithms (EAs). We also describe offline and online metaheuristics as examples of explicit methods to leverage this knowledge. We illustrate the benefits of this approach with four real-world applications. The first application is automated insurance underwriting-a discrete classification problem, which requires a careful tradeoff between the percentage of insurance applications handled by the classifier and its classification accuracy. The second application is flexible design and manufacturing-a combinatorial assignment problem, where we optimize design and manufacturing assignments with respect to time and cost of design and manufacturing for a given product. Both problems use metaheuristics as a way to encode domain knowledge. In the first application, the EA is used at the metalevel, while in the second application, the EA is the object-level problem solver. In both cases, the EAs use a single-valued fitness function that represents the required tradeoffs. The third application is a lamp spectrum optimization that is formulated as a multiobjective optimization problem. Using domain customized mutation operators, we obtain a well-sampled Pareto front showing all the nondominated solutions. The fourth application describes a scheduling problem for the maintenance tasks of a constellation of 25 low earth orbit satellites. The domain knowledge in this application is embedded in the design of a structured chromosome, a collection of time-value transformations to reflect static constraints, and a time-dependent penalty function to prevent schedule collisions.     

Fuzzy programming for mixed-integer optimization problems

Mixed-integer optimization problems belong to the group of NP-hard combinatorial problems. Therefore, they are difficult to search for global optimal solutions. Mixed-integer optimization problems are always described by precise mathematical programming models. However, many practical mixed-integer optimization problems have inherited a more or less imprecise nature. Under these circumstances, if we take into account the flexibility of the constraints and the fuzziness of the objectives, the original mixed-integer optimization problems can be formulated as fuzzy mixed-integer optimization problems. Mixed-integer hybrid differential evolution (MIHDE) is an evolutionary search algorithm which has been successfully applied to many complex mixed-integer optimization problems. In this article, a fuzzy mixed-integer mathematical programming model is developed to formulate the fuzzy mixed-integer optimization problem. In addition the MIHDE is introduced to solve the fuzzy mixed-integer programming problem. Finally, the illustrative example shows that satisfactory results can be obtained by the proposed method. This demonstrates that MIHDE can effectively handle fuzzy mixed-integer optimization problems.     

Approach to decision making in fuzzy environment

A general approach to solving a wide class of optimization problems with fuzzy coefficients in objective functions and constraints is described. It is based on a modification of traditional mathematical programming methods and consists in formulating and solving one and the same problem within the framework of interrelated models with constructing equivalent analogs with fuzzy coefficients in objective function alone. This approach allows one to maximally cut off dominated alternatives from below as well as from above. The subsequent contraction of the decision uncertainty region is associated with reduction of the problem to multicriteria decision making in a fuzzy environment. The approach is applied within the context of fuzzy discrete optimization models, that is based on a modification of discrete optimization algorithms. The results of the paper are of a universal character and are already being used to solve problems of the design and control of power systems and subsystems.     

A hybrid approach to constrained global optimization

In this paper, we propose a novel hybrid global optimization method to solve constrained optimization problems. An exact penalty function is first applied to approximate the original constrained optimization problem by a sequence of optimization problems with bound constraints. To solve each of these box constrained optimization problems, two hybrid methods are introduced, where two different strategies are used to combine limited memory BFGS (L-BFGS) with Greedy Diffusion Search (GDS). The convergence issue of the two hybrid methods is addressed. To evaluate the effectiveness of the proposed algorithm, 18 box constrained and 4 general constrained problems from the literature are tested. Numerical results obtained show that our proposed hybrid algorithm is more effective in obtaining more accurate solutions than those compared to.     

A unified approach to structural weight minimization

It is shown that the two classical approaches to structural optimization have now reached a stage where they employ the same basic principles. Indeed, the well-known optimality criteria approach can be viewed as transforming the initial problem in a sequence of simple explicit problems in which the constraints are approximated from virtual work considerations. On the other hand, the mathematical programming approaches have progressively evoluated to a linearization method using the reciprocals of the design variables — this powerful method is proven here to be identical to a generalized optimality criteria approach. Finally, new efficient methods are proposed: (a) a hybrid optimality criterion based on first-order approximations of the most critical stress constraints and zeroth-order approximations of the others and (b) a mixed method which lies between a strict primal mathematical programming method and a pure optimality criteria (or linearization) approach. Simple numerical problems illustrate the concepts established in the paper.     

HYBRID METAHEURISTICS FOR THE DESIGN OF COUPLED RESONATOR FILTERS

The design of coupled resonator filters used in many telecommunication applications poses an optimization problem that can be tackled with heuristic methods. In many configurations, simple heuristic methods do not give satisfactory results, and the combination in hybrid metaheuristics of local and global search methods is a better approach. This article analyzes the systematic development of hybrid metaheuristic methods for the design of coupled resonator filters. Engineers normally use the MATLAB computing environment to work on the design of these devices, so the available MATLAB optimization toolboxes are used here as a basis to address those optimization problems. The results obtained are in general satisfactory, and the best results are obtained in the experiments with memetic algorithms in which methods based in populations (Genetic Algorithms and Scatter Search) are combined with local search methods to improve individuals in the population at different parts of the metaheuristic.     

Hybrid genetic algorithms for timetabling

Hybrid genetic algorithms are presented that use optimization heuristics and genetic techniques to outperform all existing programs for the timetabling problem. The timetabling problem is very hard (NP-complete) and a general polynomial time deterministic algorithm is not known. An artificial intelligence approach, in a logic programming environment, may be useful for such a problem. The decomposition and classification of constraints and the constraint ordering to obtain the minimization of the backtracking and the maximization of the parallelism are illustrated. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited for this kind of problem, since there exists an easy way to assess a good timetable but not a well-structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solutions. The evaluation function and the genetic operators are well separated from the domain-specific parts, such as the problem knowledge and the heuristics, i.e., from the timetable builder. A fundamental issue and a general problem in the decision process and automated reasoning is how to efficiently obtain logic decisions under disjunctive constraints. Logic constraint satisfaction problems are in general NP-hard and a general deterministic polynomial time algorithm is not known. The present article illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favorably with the best-known programs to solve decisions problems under logic constraints. Complexity of the new algorithms and results of significant experiments are reported. © 1996 John Wiley & Sons, Inc.