A two-dimensional bin-packing problem with conflict penalties

In this paper, we address the two-dimensional bin-packing (2BP) problem with variable conflict penalties, which incur if conflicting items are loaded into the same bin. Such a problem is observed in applications such as supermarket chains and automobile components transportation. The problem not only focuses on minimisation of number of bins used, but also deals with the conflict penalties at the same time. We propose a heuristic method based on the IMA algorithm and adapt it to solve this problem. A local search procedure is also designed to further improve the solutions. For instances derived from benchmark test data, the computational results indicate that the adapted IMA heuristic algorithm with local search effectively balances the number of bins used and the conflict penalties. The algorithm outperforms several adapted approaches that are well known for the 2BP problems.     

Robust Lasso Regression Using Tukey's Biweight Criterion

The adaptive lasso is a method for performing simultaneous parameter estimation and variable selection. The adaptive weights used in its penalty term mean that the adaptive lasso achieves the oracle property. In this work, we propose an extension of the adaptive lasso named the Tukey-lasso. By using Tukey's biweight criterion, instead of squared loss, the Tukey-lasso is resistant to outliers in both the response and covariates. Importantly, we demonstrate that the Tukey-lasso also enjoys the oracle property. A fast accelerated proximal gradient (APG) algorithm is proposed and implemented for computing the Tukey-lasso. Our extensive simulations show that the Tukey-lasso, implemented with the APG algorithm, achieves very reliable results, including for high-dimensional data where p > n. In the presence of outliers, the Tukey-lasso is shown to offer substantial improvements in performance compared to the adaptive lasso and other robust implementations of the lasso. Real-data examples further demonstrate the utility of the Tukey-lasso. Supplementary materials for this article are available online.     

TOPOLOGY OPTIMIZATION OF SHEETS IN CONTACT BY A SUBGRADIENT METHOD

We consider the solution of finite element discretized optimum sheet problems by an iterative algorithm. The problem is that of maximizing the stiffness of a sheet subject to constraints on the admissible designs and unilateral contact conditions on the displacements. The model allows for zero design volumes, and thus constitutes a true topology optimization problem. We propose and evaluate a subgradient optimization algorithm for a reformulation into a non-differentiable, convex minimization problem in the displacement variables. The convergence of the method and its low computational complexity are established. An optimal design is derived through a simple averaging scheme which combines the solutions to the linear design problems solved within the subgradient method. To illustrate the efficiency of the algorithm and investigate the properties of the optimal designs, thealgorithm is numerically tested on some medium- and large-scale problems. © 1997 by John Wiley & Sons, Ltd.     

Extending capacity planning by positive lead times and optional overtime,earliness and tardiness for effective master production scheduling

In this paper we consider the problem of improving the Master Production Schedule (MPS) in make-to-order production systems when demand exceeds available resource capacity. Due to the complexity of the problem, in practice solutions are usually obtained manually. We propose an algorithm that offsets production orders guided by tardiness, earliness and overtime penalties. The intermediate tool used to determine resource utilization is Rough Cut Capacity Planning (RCCP) extended by positive lead times and options for overtime, earliness and tardiness. This approach leads to a more realistic resource loading calculation, similar to CRP but without its computational burden. The discrete optimization model is solved by a Genetic Algorithm (GA); within the GA, delays or early deliveries of each order are represented as genes of a chromosome. The method is tested against systematically developed benchmark problems and real industrial data. Improvements over the traditional RCCP procedure and an ERP's embedded routines are demonstrated by the computational results and support the applicability of the proposed approach for real-life make-to-order environments.     

Piecewise linear elastic–plastic analysis

The purpose of this paper is to show that a mathematical programming method, due to Maier and his co-workers, of nonlinear structural analysis can be rerformulated so that greater computational efficiences are achived. The methods are designed for a class of elastic–plastic structures under ‘piecewise linear’ assumptions and solve among others the problem of determining the stresses and strains in the structure. The reformulation gives rise to a class of mathematical programming problems calles a ‘n by dn linear complementarity problem’, for which the author has developed an efficient algorithm. It will be explained why and by how much the proposed method (the reformulation and its solution by the author's algorithm) solves the structural problems more efficiently than the existing one. Results of a systematic computer experiment supporting the efficiency of the proposed method are also presented.     

Fast Algorithms for the Round Trip Location Problem

This paper presents several fast algorithms for the round trip location problem. I show how to simplify the method given in an article by Chan and Hearn in which only the rectilinear case is addressed and get an algorithm with improved complexity for a given accuracy. An exact solution algorithm (the complexity of which is unknown) that solved test data problems even faster is presented and generalized for Euclidean and ℓ_p distances. Computational results are also presented.     

Scheduling with generalized batch delivery dates and earliness penalties

In this paper, we study some single machine scheduling problems with generalized batch delivery dates and earliness penalties. The generalized delivery dates are given a-priori before any jobs are processed. They are unrelated to the jobs and the processing order. Each specific delivery batch contains jobs completed but undelivered until the specific delivery date. We consider scheduling problems to minimize two types of earliness penalties: one is the total earliness; the other is the maximum earliness. For these two problems, first we show that they are NP-hard in the strong sense for general cases; then we prove that they are still NP-hard even if there are only two generalized batch dates. We also prove that they are solved in polynomial time for general earliness penalty function if all processing times are equal, and give an O(n log(n)) algorithm to solve the weighted earliness cases.     

A multi-item multi-packaging model to minimise cost of lost units,unpacking cost and CO2 emissions

This paper presents two multi-objective models that integrate packaging size and production scheduling problems for a flexible flow shop system. The main objective is to find the packaging size of finished product per item and the production schedule that would minimise cost of lost units, unpacking cost, inventory cost, earliness/tardiness penalties and kilograms of carbon dioxide emitted by resources operation. Since the complexity of the proposed models, a Pareto-based hybrid genetic algorithm (HGA) is also developed. A case study was developed to analyse the performance of both models using different instances. Numerical results indicate that the outperformance of one model over the other depends on the demand and the packaging size.     

A mathematical programming method for the inelastic analysis of reinforced concrete frames

A mathematical programming method is presented for solving problems of (i) determining the moments and rotations and (ii) determining the safety factor of reinforced concrete frames. The proposed method is essentially a reformulation of those developed by De Donato and Maier. However, the reformulation results in a new mathematical programming model for which an efficient algorithm is developed. The advantage of the proposed method is mainly computational; in fact it requires roughly one half computer time and storage space as compared with those De Donato and Maier employ to solve the same problem.     

A discrete electromagnetism-like mechanism for parallel machine scheduling under a grade of service provision

We consider the problem of minimising total weighted tardiness on identical parallel machines with grade of service eligibility. Due to the essential complexity of the problem, we apply an electromagnetism-like mechanism (EM), which is a novel metaheuristic, to solve the problem. In the proposed EM, the particle is redesigned to represent a valid assignment of jobs to machines. A distance measure between particles, called ‘1A2B’ distance, is proposed by the concept of a number guessing game. Then, the new attraction and repulsion operators are developed to move a particle to the new particle. To verify the proposed EM, computational experiments are conducted to make a comparison with a recent genetic algorithm (GA). The results show that the proposed EM has a good performance and outperforms the GA for the considered problem.     

基于“码袋”算法的话者自动辨认系统

在话者自动辨认系统中,话者数量是决定辨认时间的最主要因素。因而在大数量注册话者的辨认中如何减少辨认所需要的运算时间是一个关键问题。针对这一问题,提出了一种新的基于＂码袋＂的话者模型设计算法,它通过统计＂码袋＂中每个码字在话者语音中的概率分布来实现话者模型的设计。实验结果表明该算法在保证较高辨认率的同时,有效地降低了话者自动辨认系统的计算复杂度。     

Stochastic dynamic modeling of short gene expression time-series data

In this paper, the expectation maximization (EM) algorithm is applied for modeling the gene regulatory network from gene time-series data. The gene regulatory network is viewed as a stochastic dynamic model, which consists of the noisy gene measurement from microarray and the gene regulation first-order autoregressive (AR) stochastic dynamic process. By using the EM algorithm, both the model parameters and the actual values of the gene expression levels can be identified simultaneously. Moreover, the algorithm can deal with the sparse parameter identification and the noisy data in an efficient way. It is also shown that the EM algorithm can handle the microarrary gene expression data with large number of variables but a small number of observations. The gene expression stochastic dynamic models for four real-world gene expression data sets are constructed to demonstrate the advantages of the introduced algorithm. Several indices are proposed to evaluate the models of inferred gene regulatory networks, and the relevant biological properties are discussed.     

Product decomposition strategy for optimization of supply chain planning

Optimization of large-scale supply chain planning models requires the application of decomposition strategies to reduce the computational expense. Two major options are to use either spatial or temporal Lagrangean decomposition. In this paper, to further reduce the computational expense a novel decomposition scheme by products is presented. The decomposition is based on a reformulation of knapsack constraints in the problem. The new approach allows for simultaneous decomposition by products and by time periods, enabling the generation of a large number of subproblems, that can be solved by using parallel computing. The case study shows that the proposed product decomposition exhibits similar performance as the temporal decomposition, and that selecting different orders of products and aggregating the linking constraints can improve the efficiency of the algorithm.     

Modeling Regression Quantile Process Using Monotone B-Splines

Quantile regression as an alternative to conditional mean regression (i.e., least-square regression) is widely used in many areas. It can be used to study the covariate effects on the entire response distribution by fitting quantile regression models at multiple different quantiles or even fitting the entire regression quantile process. However, estimating the regression quantile process is inherently difficult because the induced conditional quantile function needs to be monotone at all covariate values. In this article, we proposed a regression quantile process estimation method based on monotone B-splines. The proposed method can easily ensure the validity of the regression quantile process and offers a concise framework for variable selection and adaptive complexity control. We thoroughly investigated the properties of the proposed procedure, both theoretically and numerically. We also used a case study on wind power generation to demonstrate its use and effectiveness in real problems. Supplementary materials for this article are available online.     

Solving personnel tour scheduling problems using the dual all-integer cutting plane

Personnel tour scheduling problems are highly relevant to service organizations and have recently received considerable attention in both theory and practice. The inherent complexity of generalized set-covering formulations (GSCFs) of personnel tour scheduling problems has often resulted in the deployment of LP-based and local-search heuristic procedures, even for relatively small problems. This paper evaluates the performance of the dual all-integer cutting plane for solving such problems. A computational study revealed that the cutting plane, enhanced by an LP objective cut and sophisticated source row selection rule, substantially outperformed a commercial branch and bound code across four sets of test problems. The study also showed that an advanced starting solution based on the LP relaxation of the GSCF generally provided more rapid convergence of the algorithm.     

A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

Triangular finite elements for the generalized Bessel equation of order m

A new family of triangular finite elements is described, useful for solving the axisymmetric vector Helmholtz equation, and a variety of scalar Helmholtz equation problems which lead to generalized Bessel equations of some order m. This family is similar in principle to the scalar axisymmetric Helmholtz elements derived earlier, but requires both reformulation of its describing equations and corresponding new universal element matrices, for successful computational implementation. The necessary formulation is given in this paper. Matrix elements to the sixth-order inclusive have been calculated and extensively tested computationally.     

A distributed algorithm for fitting generalized additive models

Generalized additive models are an effective regression tool, popular in the statistics literature, that provides an automatic extension of traditional linear models to nonlinear systems. We present a distributed algorithm for fitting generalized additive models, based on the alternating direction method of multipliers (ADMM). In our algorithm the component functions of the model are fit independently, in parallel; a simple iteration yields convergence to the optimal generalized additive model. This is in contrast to the traditional approach of backfitting, where the component functions are fit sequentially. We illustrate the method on different classes of problems such as generalized additive, logistic, and piecewise constant models, with various types of regularization, including those that promote smoothness and sparsity.     

Reliability-based optimal structural design by the decoupling approach

A decoupling approach for solving optimal structural design problems involving reliability terms in the objective function, the constraint set or both is discussed and extended. The approach employs a reformulation of each problem, in which reliability terms are replaced by deterministic functions. The reformulated problems can be solved by existing semi-infinite optimization algorithms and computational reliability methods. It is shown that the reformulated problems produce solutions that are identical to those of the original problems when the limit-state functions defining the reliability problem are affine. For nonaffine limit-state functions, approximate solutions are obtained by solving series of reformulated problems. An important advantage of the approach is that the required reliability and optimization calculations are completely decoupled, thus allowing flexibility in the choice of the optimization algorithm and the reliability computation method.