A fork is a graph that is obtained from K-1,K-3 by subdividing one edge. It is known [6-8] that for K-1,K-3-free graphs the problem of finding the largest independent set can be solved in a polynomial time. In this pa...
详细信息
A fork is a graph that is obtained from K-1,K-3 by subdividing one edge. It is known [6-8] that for K-1,K-3-free graphs the problem of finding the largest independent set can be solved in a polynomial time. In this paper, we prove that this is also true for the wider class of fork-free graphs. (C) 2002 Elsevier B.V. All rights reserved.
In this paper we consider the open shop problem with unit processing times and tree constraints (outtree) between the jobs. The complexity of this problem was open. We present a polynomial algorithm which decomposes t...
详细信息
In this paper we consider the open shop problem with unit processing times and tree constraints (outtree) between the jobs. The complexity of this problem was open. We present a polynomial algorithm which decomposes the problem into subproblems by means of the occurrence of unavoidable idle time. Each subproblem can be solved on the base of an algorithm for the corresponding open shop problem without tree constraints.
In a paper published in the International Journal of Production Economics (IJPE) [Zhang, R., Kaku, I., Xiao, Y., 2012. Model and heuristic algorithm of the joint replenishment problem with complete backordering and co...
详细信息
In a paper published in the International Journal of Production Economics (IJPE) [Zhang, R., Kaku, I., Xiao, Y., 2012. Model and heuristic algorithm of the joint replenishment problem with complete backordering and correlated demand. International Journal of Production Economics 139 (1), 33-41], the authors proposed a joint replenishment problem (JRP) model with complete backordering and correlated demand caused by cross-selling. The model was transformed into minimizing a function with respect to multiples of a major item's order cycle, and a heuristic algorithm was developed for near-optimal solutions. In this paper, we reinvestigate the problem and analyze the mathematical property of the model to develop an exact algorithm. The algorithm can obtain global optima and exhibits polynomial complexity.
For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a ...
详细信息
For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways:One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space.
Heterogeneity is a fact of life in computer networks. Increasing attention is being given to provide "global" connectivity by building gateways to accommodate heterogeneous elements in a network. One of the ...
详细信息
Heterogeneity is a fact of life in computer networks. Increasing attention is being given to provide "global" connectivity by building gateways to accommodate heterogeneous elements in a network. One of the key problems in synthesizing gateways is protocol conversion. Protocol converters "translate" messages from one set of protocols to another so as to overcome mismatches in the interconnection. Despite the importance of this problem, most protocol converters have been built in an ad hoc manner. We present a systematic procedure to synthesize protocol converters from formal specifications. Compared to the other procedures reported in the literature, which take exponential time, our procedure takes only polynomial time in the size of protocols. Our algorithm proceeds in two steps: a) compute the largest common subset of services provided by the two mismatched protocols;and b) reduce the converter, retaining common services, without traversing the entire machine that represents the composition of the two mismatched protocols. In a number of cases, the converter can be constructed by a "memoryless" translation of messages from one protocol to another. We give conditions under which such stateless conversion is possible. We present two examples to illustrate our techniques. In the first example, we compute a converter that interconnects a half-duplex protocol with a full-duplex protocol from their formal specifications. A trivially constructed protocol converter for these protocols has 33 936 states, while the number of states in the converter generated by our procedure is only 336. Our second example, illustrates the polynomial procedure applied to computation of a converter for interconnecting the SNR and TCP protocols. A brute force computation would be exponential and therefore infeasible, whereas our algorithm computes the converter in about 10 seconds on a Sun SparcStation 1+.
The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to def...
详细信息
The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.
In this article, we deal with graphs modelling interconnection networks of parallel systems (parallel computers, networks of workstations, etc.). We want to share the nodes of such a network between many users, each o...
详细信息
In this article, we deal with graphs modelling interconnection networks of parallel systems (parallel computers, networks of workstations, etc.). We want to share the nodes of such a network between many users, each one needing a given number of nodes. Thus, a graph G with N vertices is said to be decomposable if for each set {n(1),...,n(k)} whose sum is equal to N, there exists a partition V-1,...,V-k of V(G) such that for each i, 1less than or equal toiless than or equal tok, |V-i| = n(i) and the subgraph induced by V-i is connected. We show that determining whether a given tripode (three disjoint chains connected by one extremity to a same new vertex) is decomposable can be done by a polynomial algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.
This paper addresses the multi-robot 2-cyclic scheduling problem in a no-wait robotic cell where exactly two parts enter and leave the cell during each cycle and multiple robots on a single track are responsible for t...
详细信息
This paper addresses the multi-robot 2-cyclic scheduling problem in a no-wait robotic cell where exactly two parts enter and leave the cell during each cycle and multiple robots on a single track are responsible for transporting parts between machines. We develop a polynomial algorithm to find the minimum number of robots for all feasible cycle times. Consequently, the optimal cycle time for any given number of robots can be obtained with the algorithm. The proposed algorithm can be implemented in O(N(7)) time, where N is the number of machines in the considered robotic cell. (C) 2010 Elsevier Ltd. All rights reserved.
This paper addresses cyclic hoist scheduling in a no-wait electroplating line where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages. We prove that suc...
详细信息
This paper addresses cyclic hoist scheduling in a no-wait electroplating line where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages. We prove that such an extended problem can be solved in polynomial time. (C) 2004 Published by Elsevier B.V.
This paper addresses a real-life production planning problem arising in a manufacturer of luxury goods. This problem can be modeled as a single item dynamic lot-sizing model with backlogging, outsourcing and inventory...
详细信息
This paper addresses a real-life production planning problem arising in a manufacturer of luxury goods. This problem can be modeled as a single item dynamic lot-sizing model with backlogging, outsourcing and inventory capacity. Setup cost is included in the production cost function, and the production level at each period is unbounded. The holding, backlogging and outsourcing cost functions are assumed to be linear. The backlogging level at each period is also limited. The goal is to satisfy all demands in the planning horizon at minimal total cost. We show that this problem can be solved in O(T-4 logT) time where T is the number of periods in the planning horizon. (C) 2012 Elsevier Ltd. All rights reserved.
暂无评论