In this paper a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time functi...
详细信息
In this paper a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time function p(t) has to be processed on a single machine. The objective is to find a Pareto-optimal set of schedules with respect to the criteria phi(max) and makespan, wherer phi(max) is a non decreasing function depending on the completion times of the jobs. We present an approach that allows to find an optimal schedule with respect to different scheduling criteria, such as the minimization of makespan, lateness or weighted lateness, tardiness and weighted tardiness etc. in time polyneffnially depending on the number of jobs. The complexity of the presented algorithm is O(n(3)max{flog n, H, P}), where H and P are the complexity of calculating phi(j)(t) and p(t), respectively. (C) 2016, IFAC (Informational rederation of Automatic Control) Hosting Elsevier Ltd. All rights reserved.
polynomial algorithms for solving the quadratic assignment problem on special types of networks are proposed. The structure of the links between the objects to be located is represented by a graph.
polynomial algorithms for solving the quadratic assignment problem on special types of networks are proposed. The structure of the links between the objects to be located is represented by a graph.
We consider the bipartite unconstrained 0-1 quadratic programming problem (BQP01) which is a generalization of the well studied unconstrained 0-1 quadratic programming problem (QP01). BQP01 has numerous applications a...
详细信息
We consider the bipartite unconstrained 0-1 quadratic programming problem (BQP01) which is a generalization of the well studied unconstrained 0-1 quadratic programming problem (QP01). BQP01 has numerous applications and the problem is known to be MAX SNP hard. We show that if the rank of an associated m x n cost matrix Q = (q(ij)) is fixed, then BQP01 can be solved in polynomial time. When Q is of rank one, we provide an O(n log n) algorithm and this complexity reduces to O(n) with additional assumptions. Further, if q(ij) = a(i) + b(j) for some a(i) and b(j), then BQP01 is shown to be solvable in O(mn log n) time. By restricting m = O(log n), we obtain yet another polynomially solvable case of BQP01 but the problem remains MAX SNP hard if m = O(k root n) for a fixed k. Finally, if the minimum number of rows and columns to be deleted from Q to make the remaining matrix non-negative is O(log n), then we show that BQP01 is polynomially solvable but it is NP-hard if this number is O(k root n) for any fixed k. (C) 2015 Elsevier B.V. All rights reserved.
We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than...
详细信息
We consider a random sparse graph with bounded average degree, in which a subset of vertices has higher connectivity than the background. In particular, the average degree inside this subset of vertices is larger than outside (but still bounded). Given a realization of such graph, we aim at identifying the hidden subset of vertices. This can be regarded as a model for the problem of finding a tightly knitted community in a social network, or a cluster in a relational dataset. In this paper we present two sets of contributions: (i) We use the cavity method from spin glass theory to derive an exact phase diagram for the reconstruction problem. In particular, as the difference in edge probability increases, the problem undergoes two phase transitions, a static phase transition and a dynamic one. (ii) We establish rigorous bounds on the dynamic phase transition and prove that, above a certain threshold, a local algorithm (belief propagation) correctly identify most of the hidden set. Below the same threshold no local algorithm can achieve this goal. However, in this regime the subset can be identified by exhaustive search. For small hidden sets and large average degree, the phase transition for local algorithms takes an intriguingly simple form. Local algorithms succeed with high probability for and fail for (with , the average degrees inside and outside the community). We argue that spectral algorithms are also ineffective in the latter regime. It is an open problem whether any polynomial time algorithms might succeed for deg(in) - deg(out) < root deg(out) /e.
The following case of the classical NP-hard scheduling problem is considered. There is a set of jobs N with identical processing times p = const. All jobs have to be processed on a single machine. The objective functi...
详细信息
The following case of the classical NP-hard scheduling problem is considered. There is a set of jobs N with identical processing times p = const. All jobs have to be processed on a single machine. The objective function is minimization of maximum lateness. We analyze algorithms for the makespan problem, presented by Garey et al. (1981) and Simons (1978) and represent two polynomial algorithms to solve the problem and to construct the Pareto set with respect to criteria L-max and C-max. The complexity of presented algorithms equals O(Q center dot n log n) and O(n(2) log n), where 10(-Q) is the accuracy of the input-output parameters. (C) 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
The following case of the classical NP-hard scheduling problem is considered. There is a set of jobs N with identical processing times p = const. All jobs have to be processed on a single machine. The objective functi...
详细信息
The following case of the classical NP-hard scheduling problem is considered. There is a set of jobs N with identical processing times p = const. All jobs have to be processed on a single machine. The objective function is minimization of maximum lateness. We analyze algorithms for the makespan problem, presented by Garey et al. (1981) and Simons (1978) and represent two polynomial algorithms to solve the problem and to construct the Pareto set with respect to criteria L max and C max . The complexity of presented algorithms equals O(Q n log n ) and O( n 2 log n ), where 10 - Q is the accuracy of the input-output parameters.
The SPERT problem was defined, in a game theory framework, as the fair allocation of the slack or float among the activities in a PERT network previous to the execution of the project. Previous approaches tackle with ...
详细信息
The SPERT problem was defined, in a game theory framework, as the fair allocation of the slack or float among the activities in a PERT network previous to the execution of the project. Previous approaches tackle with this problem imposing that the durations of the activities are deterministic. In this paper, we extend the SPERT problem into a stochastic framework defining a new solution that tries also to maintain the good performance of some other approaches that have been defined for the deterministic case. Afterward, we present a polynomial algorithm for this new solution that also could be used for the calculation of other approaches founded in the deterministic SPERT literature.
We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job process...
详细信息
We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.
An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, ...
详细信息
An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O(n(4)) time. However, for the special cases of Koopmans-Beckmann QAP and the multiplicative assignment problem the input size is of Omega(n(2)). We show that the QAP linearization problem for these special cases can be solved in O(n(2)) time. For symmetric Koopmans-Beckmann QAP, Bookhold [I. Bookhold, A contribution to quadratic assignment problems, Optimization 21 (1990) 933-943.] gave a sufficient condition for linearizability and raised the question if the condition is necessary. We show that Bookhold's condition is also necessary for linearizability of symmetric Koopmans-Beckmann QAP. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论