The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.

In this paper we deal with the problem of deciding the best assortment and cut of defective bidimensional stocks. The problem, originating in a glass manufacturing process, can arise in various industrial contexts. We propose a novel bilevel programming approach describing a competition between two decision makers with contrasting objectives: one aims at fulfilling production requirements, the other at generating defects that, damaging the products, reduce yield as much as possible. By exploiting nice properties of adversarial optimal solutions, the bilevel program is rewritten as a one-level 0-1 linear program. Computational results achieved on random instances with realistic features are discussed, showing the quality and the benefits of the proposed approach in reducing the yield loss from defective material in a worst-case perspective.

Cutting operations in manufacturing are characterized by practical requirements and utility criteria that usually increase the complexity of formulations or, even worse, are difficult to be modeled in terms of mathematical programming. However, disregarding or just simplifying those requirements often leads to solutions considered not attractive or even useless by the manufacturer. In this paper we consider a rich two-dimensional cutting stock problem that covers the whole specification of a family of wood cutting machines produced by a worldwide leader in industrial machinery manufacturing. A sequential value correction heuristic is implemented to minimize the employed stock area while reducing additional objective functions.

We study an operation scheduling problem where a finite set of jobs with due dates must be completed by one machine: each job is completed as soon as a specific subset of unit operations is done. Distinct jobs may share operations, and when an operation is done, it is done for all the jobs that share it. The goal is to schedule operations so that the (weighted) number of tardy jobs is minimized. We reformulate the problem as maximum stable set problem on a special graph and study its structure. Valid inequalities and optimality cuts are derived, separated, and tested in a computational experience that identifies some features of hard instances and the potential contribution of the addition, at root, of various cut classes. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 306–320 2014

Abstract We discuss two formulations of the pattern minimization problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore‐Gomory. Let z (u) be the bound given by the linear relaxation of (i) under a given vector u of parameters. We show that z (u) ≥ z (u) and provide a class of instances for which the inequality holds strict. We observe that the linear relaxation of both formulations can be solved by the same column generation procedure and discuss the critical role of parameter u. The article is completed by a numerical test comparing the lower bounds obtained through (1) and (2) for different values of u. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract We investigate polyhedral properties of the following scheduling problem: given two sets of unit, indivisible jobs and revenue functions of the jobs completion times, find a one‐machine schedule maximizing the total revenue under the constraint that the schedule of each job set respects a prescribed chain‐like precedence relation. A solution to this problem is an order preserving assignment of the jobs to a set of time‐slots. We study the convex hull of the feasible assignments and provide families of facet‐defining inequalities in two cases: (i) each job must be assigned to a time‐slot and (ii) a job does not need to be assigned to any time‐slot. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Mass customization requires us to select a few types of resources to produce heterogeneous classes of products. In the assortment problem addressed here, a resource unit of type j yields, at a cost cij, a batch of aij product units of type i. The problem, a generalization of the p-median, calls for (i) choosing a restricted subset of resource types and (ii) assigning resource units to products so as to fulfill a given demand vector at a minimum cost. For this problem, we develop a branch-and-price scheme that can either be used to find optimal solutions, or tuned by choosing columns in a suitable class so as to get approximate solutions. The solutions obtained in the second case approach the optimum by a ratio that asymptotically reduces to zero as the demand of the least-required product increases. A comparative analysis of the features of the algorithm is discussed for a wide set of large problem instances.

Abstract This article investigates a two‐user competitive scheduling problem. The problem arises in a Universal Mobile Telecommunication System (UMTS) developed within the European IST project FUTURE: given two mobile terminals, one wants to maximize the on‐time data packets transmitted to one user, while guaranteeing a certain amount of on‐time data packets to the other. We show that the problem is NP‐hard, despite peculiar properties of data and solutions. We propose a fast lagrangian heuristic able to cope with a severe real‐time requirement, and compare it to a greedy‐like heuristic on a set of practical instances. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 132–141 2004

This paper deals with models for flow management problems in flexible assembly systems (FASs). The system consists of a set of machines that must perform the assembly of a number of parts, possibly of different types. Each part type requires a set of operations; the precedence relations among the operations are specified by an assembly tree. Machines are provided with limited-capacity tool magazines and a finite buffer for holding parts. Each machine can be tooled to perform only a particular subset of the operations required by the whole process. One problem is that of finding a feasible assignment of operations to machines and a feasible schedule of the subassemblies in order to minimize the completion time of all of the parts. In this paper, the problem is analysed as a case of pipelined assembly, i.e., when the FAS is characterized by a serial transportation system (flow line) and there exist a dominating path in the assembly tree. We present polynomial-time dynamic programming algorithms for solving the problem for both single-type and multi-type production.>

The authors deal with the problem of part flow management in a class of assembly systems characterized by a serial transportation system connecting the workstations. The system assembles a number of identical units, each requiring a set of operations. Each operation is performed by a workstation and each workstation can perform any operation. The problem consists of assigning the operations to the workstations to maximize some productivity index of the system. Usually, a tree-like precedence relationship exists among the operations (assembly tree). The problem is analyzed for the case in which a dominating path on the assembly tree exists. A polynomial time dynamic programming algorithm is presented for the optimal assignment of operations to workstations.>

Abstract We consider the problem of predicting whether a deadlock will necessarily occur in a store‐and‐forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this problem are shown to be NP‐complete even for simple classes of graphs (among others bipartite graphs, two terminal series‐parallel [TTSP] graphs and therefore planar graphs). On the other hand, the same problems are shown to be polynomially solvable for treelike networks. In this case, two efficient algorithms for checking whether a treelike network with n vertices and p packets is bound to deadlock are proposed. The former has an O(pn) time and space complexity, whereas the latter runs in O(n log n)1 time and requires O(n) space. In the case of multibuffered networks, both versions of the problem are shown to be NP‐complete even on treelike networks.

The problem of part routing and scheduling in flexible manufacturing systems is considered with the goal of increasing the throughput. The flexible system considered is strongly characterized by the inclusion of assembly among the manufacturing operations to be performed on a mix of part batches. In particular, the logic structure of some basic decision problems is indicated through a set of combinatorial models. Two basic assembly problems characterized by batches of large and small size, respectively, are analyzed.>