A Heuristic Algorithm for Sequencing on One Machine to Minimize Total Tardiness

The problem of minimizing total tardiness assumes that the N jobs to be processed on a single machine are simultaneously available at time zero. Since due dates and sequence-independent processing times are known, the problem is to determine a processing sequence, from the N! possible sequences, which minimizes the sum of tardiness for all the jobs in the set. The powerful dominance theorems of Emmons are exploited with a new heuristic procedure, avoiding enumeration of all possible sequences. For large problems, often any one of many jobs can be processed first with no change in total tardiness; however, the set of jobs which can occupy the last position in an optimal sequence is much more limited, and easily identified by application of special dominance properties. The heuristic uses Net Benefit of Relocation (NBR) analysis to determine which job should come last to reduce total tardiness. The simplicity of the algorithm enables manual solutions to small problems. Experimentation indicates that the NBR heuristic offers vast improvement over the adjacent pairwise interchange (API) heuristic of Fry et al., both in solution quality and computational effort. The NBR heuristic also performs well compared with the optimizing routine of Potts and Van Wassenhove, especially in the case of large problems where a modest growth in total tardiness is accompanied by drastically reduced computer requirements.     

Evaluation of greedy,myopic and less-greedy heuristics for the single machine,total tardiness problem

Simple, yet highly effective modifications to the net benefit of relocation (NBR) heuristic of Holsenback and Russell provide significant improvements in solution quality without any increase in computational effort by tempering the greedy nature of the original NBR heuristic. Two lemmas reduce the size of the search while adhering to optimality conditions. Experimentation compares the modified NBR heuristic (M-NBR) with the two leading heuristics of the literature. Testing on 25, 50 and 100-job problems over a wide range of due dates and tardiness factors shows the M-NBR algorithm to be the best single-pass heuristic to date. We show that a composite heuristic, employing the better of the M-NBR and another leading heuristic solution, consistently produces near-optimal solutions with negligible CPU requirements.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

An optimal solution to a three echelon supply chain network with multi-product and multi-period

Recently, Kadadevaramath et al. (2012) [1] presented a mathematical model for optimizing a three echelon supply chain network. Their model is an integer linear programming (ILP) model. In order to solve it, they developed five algorithms; four of them are based on a particle swarm optimization (PSO) method and the other is a genetic algorithm (GA). In this paper, we develop a more general mathematical model that contains the model developed by Kadadevaramath et al. (2012) [1]. Furthermore, we show that all instances proved in Kadadevaramath et al. (2012) [1] can easily be solved optimally by any integer linear programming solver.     

An integer-programming-based heuristic for the balanced loading problem

This paper presents an efficient heuristic algorithm for the one-dimensional loading problem in which the goal is to pack homogeneous blocks of given length and weight in a container in such a way that the center of gravity of the packed blocks is as close to a target point as possible. The proposed algorithm is based on the approximation of this problem as a knapsack problem. This algorithm has the same computational complexity but a better worst-case performance than the algorithm recently proposed by Amiouny et al. [Oper. Res. 40 (1992) 238]. Moreover, the computational results also show that, in general, it performs better on randomly generated problems.     

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

Extremal A-statistical limit points via ideals

In this paper, following the line of recent work of Savaş et al. [20] we apply the notion of ideals to A-statistical limit superior and inferior for a sequence of real numbers.     

An improved solution to the replenishment policy for the EMQ model with rework and multiple shipments

Recently, Chiu et al. (2012) [1] present an alternative optimization procedure to derive the optimal replenishment lot size for an economic manufacturing quantity (EMQ) model with rework and multiple shipments. This inventory model was proposed by Chiu et al. (2011) [2]. Both papers do not consider the determining of the number of shipments. This paper determines both the optimal replenishment lot size and the optimal number of shipments jointly. The solution of this paper is better than the solutions of Chiu et al.  and .     

State estimation for partially observed jump processes

In this paper partially observed jump processes are considered and optimal filtering equations are given for the conditional expectation of a functional on the past of the process.Rudemo [6] derived filtering equations for a partially observed jump Markov process. Snyder [3] gives equations for the conditional characteristic function of a jump process. Segall et al. [2] discuss filtering for processes with counting observations. Their work carries over to processes with counting observations the martingale methods that Fujisaki et al. [1] had used to derive nonlinear filtering equations for processes governed by Ito equations. Many further references to filtering for processes with discrete state measurements are given in the references cited.The objective of this paper is to show that by making use of the concept of a representation of a functional the idea of Rudemo's proof of [6, pp. 595–599] can be carried over to jump processes. The author feels that this is a very interesting proof because of its simplicity. It involves only calculations with conditional expectations and the rule for differentiation of a quotient.     

Minimizing weighted earliness–tardiness and due-date cost with unit processing-time jobs

The classical single-machine scheduling and due-date assignment problem of Panwalker et al. [Panwalker, S.S., Smith, M.L., Seidmann, A., 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30(2) (1982) 391–399] is the following: All n jobs share a common due-date, which is to be determined. Jobs completed prior to or after the due-date are penalized according to a cost function which is linear and job-independent. The objective is to minimize the total earliness–tardiness and due-date cost. We study a generalized version of this problem in which: (i) the earliness and tardiness costs are allowed to be job dependent and asymmetric and (ii) jobs are processed on parallel identical machines. We focus on the case of unit processing-time jobs. The problem is shown to be solved in polynomial (O(n⁴)) time. Then we study the special case with no due-date cost (a classical problem known in the literature as TWET). We introduce an O(n³) solution for this case. Finally, we study the minmax version of the problem, (i.e., the objective is to minimize the largest cost incurred by any of the jobs), which is shown to be solved in polynomial time as well.     

On-line construction of position heaps

We propose a simple linear-time on-line algorithm for constructing a position heap for a string (Ehrenfeucht et al., 2011 [8]). Our definition of position heap differs slightly from the one proposed in Ehrenfeucht et al. (2011) [8] in that it considers the suffixes ordered in the descending order of length. Our construction is based on classic suffix pointers and resembles Ukkonenʼs algorithm for suffix trees (Ukkonen, 1995 [17]). Using suffix pointers, the position heap can be extended into the augmented position heap that allows for a linear-time string matching algorithm (Ehrenfeucht et al., 2011 [8]).     

关于非协调位移元与杂交应力元的对应性

本文阐明了E.L.Wilson[3]等的非协调移位元与卞学鐄的杂交应力元之间所存在的对应性.     

A note on “Location of hubs in a competitive environment”

This note suggests modifications to two models for locating hubs in a competitive environment introduced by Marianov et al. [European Journal of Operational Research 114 (1999) 363–371]. They make it possible to provide optimal solutions much faster. It is also shown that the implementation of the heuristic proposed by Marianov et al. contains a flaw. Yet the heuristic itself is correct.     

Improvement in estimating the population mean in simple random sampling using information on auxiliary attribute

This paper proposes some estimators for the population mean by adapting the estimator in Singh et al. (2008) [5] to the ratio estimators presented in Kadilar and Cingi 2006 [2]. We obtain mean square error (MSE) equation for all proposed estimators, and show that all proposed estimators are always more efficient than ratio estimator in Naik and Gupta (1996) [3], and Singh et al. (2008) [5]. The results have been illustrated numerically by taking some empirical population considered in the literature.     

Texture separation via a reference set

Patch-based de-noising algorithms and patch manifold smoothing have emerged as efficient de-noising methods. This paper provides a new insight on these methods. We show how to extend them to separate oscillatory patterns that could be entangled. A collection of particular patches, that we call reference set, is selected by the user. We define a notion of similarity relative to this reference set that is used to extend the Non-Local Means (see Buades et al., 2005) [1] and the graph-based de-noising method (see Szlam et al., 2008) [12].     

Improving the feasibility pump

The feasibility pump described by Fischetti, Glover, and Lodi [M. Fischetti, F. Glover, A. Lodi, The feasibility pump, Mathematical Programming 104 (1) (2005) 91–104] and Bertacco, Fischetti, and Lodi [L. Bertacco, M. Fischetti, A. Lodi, A feasibility pump heuristic for general mixed-integer problems, Technical Report OR/05/5, DEIS–Università di Bologna, Italy, May 2005] has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, is sometimes quite poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: for 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original feasibility pump.     

A distributed dual ascent algorithm for the Hop-constrained Steiner Tree Problem

The Hop-constrained Steiner Tree Problem is often used to model applications of multicast routing with QoS requirements. This paper introduces a distributed heuristic for the problem based on the application of dual ascent over a graph transformation introduced by Gouveia et al. The proposed algorithm is shown to yield significantly better solutions than the previously known algorithms.     

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.