In this paper a one-machine scheduling model is analyzed where n different jobs are classified into K groups depending on which additional resource they require. The change-over time from one job to another consists o...
详细信息
In this paper a one-machine scheduling model is analyzed where n different jobs are classified into K groups depending on which additional resource they require. The change-over time from one job to another consists of the removal time or of the set-up time of the two jobs. It is sequence-dependent in the sense that the change-over time is determined by whether or not the two jobs belong to the same group. The objective is to minimize the make pan. This problem can be modeled as an asymmetric Traveling Salesman Problem (TSP) wit? a specially structured distance matrix. For this problem we give a polynomialtime solution algorithm that runs in O(nlogn) time. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
A fully odd K-4 is a subdivision of K-4 such that each of the six edges of the K-4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K-4 can be vertex-colored ...
详细信息
A fully odd K-4 is a subdivision of K-4 such that each of the six edges of the K-4 is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K-4 can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture.
Let G be an Eulerian digraph, and let {x(1), x(2)}, {y(1), y(2)} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x(1);x(2)}, {y(1), y(2)}) is called f...
详细信息
Let G be an Eulerian digraph, and let {x(1), x(2)}, {y(1), y(2)} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x(1);x(2)}, {y(1), y(2)}) is called feasible if there is a choice of h, i, j, k with {h, i} = { j, k} = {1, 2} such that G has two arc-disjoint x(h) x(i)- and y(j) y(k)-paths. In this paper, we characterize the structure of minimal infeasible instances, based on which an O(m + n log n) timealgorithm is presented to decide whether a given instance is feasible, where n and m are the number of vertices and arcs in the instance, respectively. If the instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m + n log n)) time.
Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governing the behavior of the network and in their objectives with respect to the ne...
详细信息
Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governing the behavior of the network and in their objectives with respect to the network. Almost all the work to date uses the unit transmission time assumption, that is, the message transmission times between all pairs of vertices are equal. In this paper, we investigated the broadcast problem under four more general transmission time assumptions. In addition, four different objective functions were considered, including the minimization of (1) the broadcast time (the maximum time for any vertex to receive the message), (2) the average time to receive the message (both with and without ready times at the vertices), (3) the weighted average time to receive the message, and (4) the cycle time. Of the 20 problems thus generated, four admit polynomial time algorithms, 15 are (in the equivalent recognition version) unary NP-complete, and the complexity status of one remains open. All these results are proved, and heuristics with an attainable constant worst-case performance ratio are provided for two of the problems for which polynomial time algorithms are not found. (C) 1998 John Wiley & Sons, Inc.
In many combinatorial situations there is a notion of independence of a set of points. Maximal independent sets can be easily constructed by a greedy algorithm, and it is of interest to determine, for example, if they...
详细信息
In many combinatorial situations there is a notion of independence of a set of points. Maximal independent sets can be easily constructed by a greedy algorithm, and it is of interest to determine, for example, if they all have the same size or the same parity. Both of these questions may be formulated by weighting the points with elements of an abelian group, and asking whether all maximal independent sets have equal weight. If a set is independent precisely when its elements are pairwise independent, a graph can be used as a model. The question then becomes whether a graph, with its vertices weighted by elements of an abelian group, is well-covered, i.e., has all maximal independent sets of vertices with equal weight. This problem is known to be co-NP-complete in general. We show that whether a graph is well-covered or not depends on its local structure. Based on this, we develop an algorithm to recognize well-covered graphs. For graphs with n vertices and maximum degree Delta, it runs in linear time if Delta is bounded by a constant, and in polynomialtime if Delta = O((3)root log n). We mention various applications to areas including hypergraph matchings and radius k independent sets. We extend our results to the problem of determining whether a graph has a weighting which makes it well-covered.
Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In ...
详细信息
Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n 2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented.
Wong,et al have studied the message routing problem to minimize the mean flow time of messages by allowing one of four parameters;origin node,destination node,release time and deadline;to be *** nonpreemptive transmis...
详细信息
Wong,et al have studied the message routing problem to minimize the mean flow time of messages by allowing one of four parameters;origin node,destination node,release time and deadline;to be *** nonpreemptive transmission,they showed that the problem is solvable in polynomialtime when destination node or deadline is allowed to be *** this paper,we continue to study the remaining two opened cases;*** origin node or release time is allowed to be *** show that it is NP-complete for each of these two cases.
In this paper, we consider single machine bi-criteria scheduling problems where jobs are from multiple job classes and there are customer orders such that each customer order consists of at least one job from each of ...
详细信息
In this paper, we consider single machine bi-criteria scheduling problems where jobs are from multiple job classes and there are customer orders such that each customer order consists of at least one job from each of the job classes. A set-up time is needed whenever the machine is changed over from a job in one class to a job in another class. One objective is to minimize the makespan which is equivalent to minimizing the total set-up time. The other objective is to minimize total carrying costs of the customer orders. The carrying cost of a customer order is measured by the length of the time interval between the completion times of the first job and the last job in the customer order. We propose constructive polynomial time algorithms for the two hierarchical scheduling problems with these two objectives, i.e. the two scheduling problems in which one objective is to be optimized while holding the other objective fixed at its optimal value.
作者：
Amoura, AKLRI
Bât. 490 Université Paris Sud 91405 Orsay Cedex France
A recent extension of the standard model, the so called multiprocessor task system, is discussed. According to this model, some tasks have to be executed on more than one processor at a time. Scheduling multiprocess...
详细信息
A recent extension of the standard model, the so called multiprocessor task system, is discussed. According to this model, some tasks have to be executed on more than one processor at a time. Scheduling multiprocessor tasks on m parallel processors in the presence of precedence constraints are discussed. Tasks are supposed to have all the same length (unit-length) and require either one or m processors for their processing. The objective of the problem is the minimization of the makespan. It is proved that any optimal scheduling algorithm for P subscript m p subscript j equals 1, prec C subscript max, i.e., the classical model, can be (efficiently) used to solve P subscript m size subscript j is an element of (1,m), p subscript j equals 1, prec C subscript max. In addition, some polynomially solvable classes of precedence graphs are derived. It is also demonstrated that no (significant) polynomial extension of this result can be expected.
We determine the computational complexity of deciding whether m polynomials in n variables have relatively prime leading terms with respect to some term order. This problem in NP-complete in general, but solvable in p...
详细信息
We determine the computational complexity of deciding whether m polynomials in n variables have relatively prime leading terms with respect to some term order. This problem in NP-complete in general, but solvable in polynomialtime in two different situations, when m is fixed and when n - m is fixed. Our new algorithm for the second case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming.
暂无评论