The parallel stack loading problem minimizing the number of reshuffles in the retrieval stage

In this paper, we consider the parallel stack loading problem (PSLP) with the objective to minimize the number of reshuffles in the retrieval stage. Since in the PSLP the incoming items have to be stored according to a fixed arrival sequence, some reshuffles cannot be avoided later on. We study two surrogate objective functions (number of unordered stackings, number of badly placed items) to estimate the number of reshuffles and compare them theoretically as well as in a computational study. For this purpose, MIP formulations and a simulated annealing algorithm are proposed.     

Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems

In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing the total weighted number of changes with bound constraints. We present an O(n ²) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a sorting problem and an inverse sorting problem. Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004).     

COMPUTATIONAL COMPLEXITY OF（2,2） PATH CHROMATIC NUMBER PROBLEM

Is there a normal Pk coloring using r colors for a given graph ? This problem is called the (k, r) path chromatic number problem of graphs. This paper proves that the (2, 2) path chromatic number problem of graphs with maximum degree 4 is NP-complete.     

Bicriteria optimization in the newsvendor problem with uniformly distributed demand

This paper analytically addresses the Bicriteria decision newsvendor problem of a retailer with the conflicting goals of maximizing the expected profit and the probability of exceeding it and obtains a closed form solution for a uniformly distributed demand. This is done by using the existence of a closed form solution for the second criterion to arrive at the solution for the Bicriteria problem. The decision variable remains the traditional order quantity intended to satisfy an uncertain demand, but there is no solution that maximizes each goal simultaneously. The search for optimality reduces to simple comparisons between parameters and the estimation of a critical weight. A numerical example is used throughout the paper to highlight the nature of the solutions and to illustrate the key properties of the various elements of the Bicriteria problem.     

On the robust assignment problem under a fixed number of cost scenarios

We investigate the complexity of the min-max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.     

Optimal number of bypasses: minimizing cost of calls to wireless phones under Calling Party Pays

In telecommunications, Calling Party Pays is a billing formula that prescribes that the person who makes the call pays its full cost. Under CPP land-line to wireless phone calls have a high cost for many organizations. They can reduce this cost at the expense of installing wireless bypasses to replace land-line to wireless traffic with wireless-to-wireless traffic, when the latter is cheaper than the former. Thus, for a given time-horizon, the cost of the project is a trade-off between traffic to-wireless and the number of bypasses. We present a method to determine the number of bypasses that minimizes the expected cost of the project. This method takes into account hourly varying traffic intensity. Our method takes advantage of parallels with inventory models for rental items. Examples illustrate the economic value of our approach.     

A note on the minimum instantaneous cost path of the dynamic traffic assignment problem

We consider an example to show that the minimum instantaneous cost path principle, as suggested in Friesz et al. [1] for generalising Wardrop's first principle to the dynamic state, may cause some drivers' routes to loop. These looping routes traverse the same link more than once - indeed, in our example six times.The work reported in this paper has been partly funded by the Science and Engineering Research Council of the United Kingdom.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

动态最小费用路在L1模下的逆问题讨论

考察动态最小费用路在L_1模下的逆问题,其中在弧费用的定义中,将弧(i,j)上的运行时间d_(ij)(t)分成最小可能运行时间d_(ij)~*和超出的运行时间(excess time)e_(ij)(t)两部分,弧(i,j)上费用即为两者赋权之和.在逆问题的讨论中考虑先将动态网络中的问题通过时间扩张网络G~T转化为静态问题,然后再利用解线性规划的逆问题的方法来解该动态最短路问题的逆问题.     

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum cost and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

Maximizing and minimizing the number of generalized colorings of trees

We classify the trees on $n$ vertices with the maximum and the minimum number of certain generalized colorings, including conflict-free, odd, non-monochromatic, star, and star rainbow vertex colorings. We also extend a result of Cutler and Radcliffe on the maximum and minimum number of existence homomorphisms from a tree to a completely looped graph on $q$ vertices.     

On minimizing the jump number for interval orders

The purpose of this paper is to give an effective characterization of all interval orders which are greedy with respect to the jump number problem.This research (Math/1406/30) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究

研究带惩罚和软容量约束的下界设施选址问题. 扩展Guha等(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)和Karger等(Karger D R,Minkoff M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329)的工作到带有惩罚的下界约束设施选址问题,提出了一个新的双标准近似算法,得到了同样的近似比ρ(1+α)/(1-α). 进一步考虑带惩罚和软容量约束的下界设施选址问题,得到了近似比为2ρ(1+α)/(1-α)的双标准近似算法.     

A presentation of the average distance minimizing problem

We talk about the following minimization problem:

Hybrid co-evolutionary particle swarm optimization and noising metaheuristics for the delay constrained least cost path problem

This paper presents a co-evolutionary particle swarm optimization (PSO) algorithm, hybridized with noising metaheuristics, for solving the delay constrained least cost (DCLC) path problem, i.e., shortest-path problem with a delay constraint on the total “cost” of the optimal path. The proposed algorithm uses the principle of Lagrange relaxation based aggregated cost. It essentially consists of two concurrent PSOs for solving the resulting minimization-maximization problem. The main PSO is designed as a hybrid PSO-noising metaheuristics algorithm for efficient global search to solve the minimization part of the DCLC-Lagrangian relaxation by finding multiple shortest paths between a source-destination pair. The auxiliary/second PSO is a co-evolutionary PSO to obtain the optimal Lagrangian multiplier for solving the maximization part of the Lagrangian relaxation problem. For the main PSO, a novel heuristics-based path encoding/decoding scheme has been devised for representation of network paths as particles. The simulation results on several networks with random topologies illustrate the efficiency of the proposed hybrid algorithm for the constrained shortest path computation problems.     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

On action minimizing measures for the Monge-Kantorovich problem

In recent years different authors ([4, 16, 17]) have noticed and investigated some analogy between Mather’s theory of minimal measures in Lagrangian dynamic and the mass transportation (or Monge-Kantorovich) problem. We replace the closure and homological constraints of Mather’s problem by boundary terms and we investigate the equivalence with the mass transportation problem. An Hamiltonian duality formula for the mass transportation and the equivalence with Brenier’s formulation are also established.     

Stochastically minimizing the number of customers in exponential queuing systems

This paper deals with the problem of controlling an exponential queuing system (that is, a system with exponential service times and Poisson arrivals) so as to stochastically minimize the number of customers in the system at any time t > 0. Sufficient (simple) conditions are developed for a policy to be optimal. Similar conditions are sufficient for a policy to stochastically minimize (maximize) any function of the state of the system. Two models are considered to illustrate the results. In both cases, optimal policies are shown to satisfy these conditions by a simple inductive procedure.