共查询到20条相似文献,搜索用时 46 毫秒
1.
In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize
makespan. We show that this problem is strongly NP-hard, and give an
time dynamic programming algorithm and an
time dynamic programming algorithm for the problem, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the setup times of all the families and the processing times of all the jobs. We further give a heuristic with
a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem. 相似文献
2.
We consider the following single machine just-in-time scheduling problem with earliness and tardiness costs: Given n jobs with processing times, due dates and job weights, the task is to schedule these jobs without preemption on a single
machine such that the total weighted discrepancy from the given due dates is minimum.
NP-hardness of this problem is well established, but no approximation results are known. Using the gap-technique, we show
in this paper that the weighted earliness–tardiness scheduling problem and several variants are extremely hard to approximate:
If n denotes the number of jobs and b∈ℕ is any given constant, then no polynomial-time algorithm can achieve an approximation which is guaranteed to be at most
a factor of O( b
n
) worse than the optimal solution unless P = NP. 相似文献
3.
We study the problem of minimizing the number of late jobs on a single machine where job processing times are known precisely and due dates are uncertain. The uncertainty is captured through a set of scenarios. In this environment, an appropriate criterion to select a schedule is to find one with the best worst-case performance, which minimizes the maximum number of late jobs over all scenarios. For a variable number of scenarios and two distinct due dates over all scenarios, the problem is proved NP-hard in the strong sense and non-approximable in pseudo-polynomial time with approximation ratio less than 2. It is polynomially solvable if the number s of scenarios and the number v of distinct due dates over all scenarios are given constants. An O( nlog? n) time s-approximation algorithm is suggested for the general case, where n is the number of jobs, and a polynomial 3-approximation algorithm is suggested for the case of unit-time jobs and a constant number of scenarios. Furthermore, an O( n s+v?2/( v?1) v?2) time dynamic programming algorithm is presented for the case of unit-time jobs. The problem with unit-time jobs and the number of late jobs not exceeding a given constant value is solvable in polynomial time by an enumeration algorithm. The obtained results are related to a min-max assignment problem, an exact assignment problem and a multi-agent scheduling problem. 相似文献
4.
We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed—in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563–1581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of \(4/3 - \varepsilon \) is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is \(O(n^2)\) for arbitrary processing times and it can be reduced to O(n) for unit processing times, where n is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.
相似文献
5.
The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I=〈( w
1, ℓ
1),( w
2, ℓ
2),…,( w
n
, ℓ
n
)〉 of n pairs of positive integers that are associated with the jobs 1,2,…, n, respectively. The processing length of job i is ℓ
i
slots where a slot is the processing time of one unit of length. The goal is to repeatedly and non-preemptively schedule
all the jobs on the fewest possible machines such that the gap (window) between two consecutive beginnings of executions of
job i is at most w
i
slots. This problem arises in push broadcast systems in which data are transmitted on multiple channels. The problem is NP-hard
even for unit-length jobs and a (1+ ε)-approximation algorithm is known for this case by approximating the natural lower bound W( I)=? i=1n(1/ wi)W(I)=\sum_{i=1}^{n}(1/w_{i}). The techniques used for approximating unit-length jobs cannot be extended for arbitrary-length jobs mainly because the optimal
number of machines might be arbitrarily larger than the generalized lower bound W( I)=? i=1n( li/ wi)W(I)=\sum_{i=1}^{n}(\ell_{i}/w_{i}). The main result of this paper is an 8-approximation algorithm for the WS problem with arbitrary lengths using new methods,
different from those used for the unit-length case. The paper also presents another algorithm that uses 2(1+ ε) W( I)+log w
max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal
for some special cases, and computational experiments show that it performs very well in practice. 相似文献
6.
This note deals with the scheduling problem of minimizing the sum of job completion times in a system with n jobs and a single machine. We investigate the on-line version of the problem where every job has to be scheduled immediately and irrevocably as soon as it arrives, without any
information on the later arriving jobs.
We prove that for any sufficiently smooth, non-negative, non-decreasing function f( n) there exists an O( f( n))-competitive on-line algorithm for minimizing the total completion time if and only if the infinite sum converges.
Received: 6 May 1997 / 3 February 1999 相似文献
7.
We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J i has an integer length ? i as well as a set T i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is “active” at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ? i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T i is a single interval, assuming that jobs are given in sorted order. For general T i , we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120–129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an \(O(\sqrt{L} m)\) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ i ? i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length. 相似文献
8.
In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and
parallel machine environment. It is shown that the feasibility problem 1|p-batch, b< n, r
j
, p
j
= p, C
j
≤ d
j
|− can be solved in O( n
2) time and that the problem of minimizing the maximum lateness can be solved in O( n
2log n) time. For the parallel machine problem P|p-batch, b< n, r
j
, p
j
= p, C
j
≤ d
j
|− an O( n
3log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O( n
3log 2
n) time. 相似文献
9.
Construction of energy-saving schedules for the execution of n jobs on a processor with the use of the dynamic voltage scaling (DVS) mechanism is considered. A formal problem statement
is presented. The problem is shown to be NP-hard. An algorithm with complexity O( n
2/ε) guaranteeing finding of a (1 + ε)-approximate solution is suggested. 相似文献
10.
This paper studies two closely related online-list scheduling problems of a set of n jobs with unit processing times on a set of m multipurpose machines. It is assumed that there are k different job types, where each job type can be processed on a unique subset of machines. In the classical definition of
online-list scheduling, the scheduler has all the information about the next job to be scheduled in the list while there is
uncertainty about all the other jobs in the list not yet scheduled. We extend this classical definition to include lookahead
abilities, i.e., at each decision point, in addition to the information about the next job in the list, the scheduler has
all the information about the next h jobs beyond the current one in the list. We show that for the problem of minimizing the makespan there exists an optimal
(1-competitive) algorithm for the online problem when there are two job types. That is, the online algorithm gives the same
minimal makespan as the optimal offline algorithm for any instance of the problem. Furthermore, we show that for more than
two job types no such online algorithm exists. We also develop several dynamic programming algorithms to solve a stochastic
version of the problem, where the probability distribution of the job types is known and the objective is to minimize the
expected makespan. 相似文献
11.
We consider the single-machine scheduling problem of minimizing the number of late jobs. We omit here one of the standard
assumptions in scheduling theory, which is that the processing times are deterministic. In this scheduling environment, the
completion times will be stochastic variables as well. Instead of looking at the expected number of on time jobs, we present
a new model to deal with the stochastic completion times, which is based on using a chance constraint to define whether a
job is on time or late: a job is on time if the probability that it is completed by the deterministic due date is at least
equal to a certain given minimum success probability. We have studied this problem for four classes of stochastic processing
times. The jobs in the first three classes have processing times that follow: (i) A gamma distribution with shape parameter
p
j
and scale parameter β, where β is common to all jobs; (ii) A negative binomial distribution with parameters p
j
and r, where r is the same for each job; (iii) A normal distribution with parameters p
j
and σ
j
2. The jobs in the fourth class have equally disturbed processing times, that is, the processing times consist of a deterministic
part and a random component that is independently, identically distributed for each job. We show that the first two cases
have a common characteristic that makes it possible to solve these problems in O( nlog n) time through the algorithm by Moore and Hodgson. To analyze the third and fourth problem we need the additional assumption
that the due dates and the minimum success probabilities are agreeable. We show that under this assumption the third problem
is
-hard in the ordinary sense, whereas the fourth problem is solvable by Moore and Hodgson’s algorithm.
We further indicate how the problem of maximizing the expected number of on time jobs (with respect to the standard definition)
can be tackled if we add the constraint that the on time jobs are sequenced in a given order and when we require that the
probability that a job is on time amounts to at least some given lower bound.
Supported by EC Contract IST-1999-14186 (Project alcom-FT). 相似文献
12.
We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one
machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem.
This result enables several cases of the server scheduling problem to be solved in O( n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum
lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted
completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented
for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup
times are equal and there are two distinct due dates. This problem is solved in O( n
3) time when all job processing times on the first machine are equal, and it is solved in O( n
4) time when all processing times on the second machine are equal.
Received November 20, 2001; revised October 18, 2002
Published online: January 16, 2003 相似文献
13.
We present hardness and approximation results for the problem of preemptive scheduling of n independent jobs on m identical parallel machines subject to a migration delay d with the objective to minimize the makespan. We give a sharp threshold on the value of d for which the complexity of the problem changes from polynomial time solvable to NP-hard. Next, we give initial results supporting
a conjecture that there always exists an optimal schedule with at most m − 1 job migrations. Finally, we provide a O( n) time (1 + 1/log 2
n)-approximation algorithm for m = 2. 相似文献
14.
Baker and Smith [J. Scheduling, 6, 7–16, 2003] introduced a new model of scheduling in which there are two or more distinct
families of jobs pursuing different objectives. Their contributions include two polynomial-time dynamic programming recursions,
respectively, for the single machine scheduling with two families of jobs to minimize a positive combination of total weighted
completion time, or maximum lateness, of the first family of jobs and maximum lateness of the second family of jobs. Unfortunately,
these dynamic programming recursions are incorrect. In this paper, we solve the same problems by an O( n1 n2( n1 + n2)) time algorithm.
Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200) 相似文献
15.
In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status
of this problem has remained open to date. We provide an O( n2) time algorithm to solve the problem. 相似文献
16.
Distance labeling schemes are composed of a marker algorithm for
labeling the vertices of a graph with short labels, coupled with a
decoder algorithm allowing one to compute the distance between
any two vertices directly from their labels (without using any additional
information).
As applications for distance labeling schemes
concern mainly large and dynamically changing networks,
it is of interest to study distributed dynamic labeling schemes.
The current paper considers the problem on dynamic trees,
and proposes efficient distributed schemes for it.
The paper first presents a labeling scheme for distances in the dynamic
tree model, with amortized message complexity O(log 2
n) per operation,
where n is the size of the tree at the time the operation takes place.
The protocol maintains O(log 2
n) bit labels.
This label size is known to be optimal even in the static scenario.
A more general labeling scheme is then introduced for the dynamic tree
model, based on extending an existing static tree labeling
scheme to the dynamic setting. The approach fits a number of
natural tree functions, such as distance, separation level, and flow.
The main resulting scheme incurs an overhead
of an O(log n) multiplicative factor in both the label size and
amortized message complexity in the case of dynamically growing
trees (with no vertex deletions).
If an upper bound on n is known in advance,
this method yields a different tradeoff, with an
O(log 2
n/log log n) multiplicative overhead on the label
size but only an O(log n/log log n) overhead on the amortized
message complexity.
In the fully dynamic model the scheme also incurs an increased
additive overhead in amortized communication, of O(log 2
n)
messages per operation. 相似文献
17.
Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may
be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in
each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair
schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. As jobs are persistent we measure
the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift
and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio less than r( m − r)/( n( q( d − 1)) + ∊ > 0; namely, it asymptotically requires r( m − r) job migrations every n( q( d − 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal
by proving a lower bound of r( m − r)/( nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for a special case when 2 q ≤ d and m = 2 r. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time. 相似文献
18.
We study the problem of scheduling jobs whose processing times are decreasing functions of their starting times. We consider the case of a single machine and a common decreasing rate for the processing times. The problem is to determine an optimal combination of the due date and schedule so as to minimize the sum of due date, earliness and tardiness penalties. We give an O( n log n) time algorithm to solve this problem. 相似文献
19.
In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the lp norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾ 1. For minimizing the lp norm, we study the case of identical machines ( s = 1) and present tight bounds as a function of p. 相似文献
20.
We study the problem of scheduling unit execution time jobs with release dates and precedence constraints on two identical
processors. We say that a schedule is ideal if it minimizes both maximum and total completion time simultaneously. We give
an instance of the problem where the min-max completion time is exceeded in every preemptive schedule that minimizes total
completion time for that instance, even if the precedence constraints form an intree. This proves that ideal schedules do
not exist in general when preemptions are allowed. On the other hand, we prove that, when preemptions are not allowed, then
ideal schedules do exist for general precedence constraints, and we provide an algorithm for finding ideal schedules in O( n
3) time, where n is the number of jobs. In finding such ideal schedules we resolve a conjecture of Baptiste and Timkovsky (Math. Methods Oper.
Res. 60(1):145–153, 2004) Further, our algorithm for finding min-max completion-time schedules requires only O( n
3) time, while the most efficient solution to date has required O( n
9) time. 相似文献
|