共查询到20条相似文献,搜索用时 17 毫秒
1.
Beat Gfeller Leon Peeters Birgitta Weber Peter Widmayer 《Journal of Combinatorial Optimization》2009,17(3):323-338
Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs
have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time,
in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm
and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed
in any order, any online algorithm has a linear competitive ratio in the worst case.
A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations
of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of
this work.
Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union.
Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich. 相似文献
2.
In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. In the first problem one can reassign several scheduled jobs in rejection tache, in the second a buffer with length k is available in rejection tache. Two optimal algorithms both with competitive ratio $\frac{3}{2}$ are presented. 相似文献
3.
Journal of Combinatorial Optimization - We consider a number of parallel-machine scheduling problems in which jobs have variable processing times. The actual processing time of each job is... 相似文献
4.
In this paper, we investigate a single-machine problem with the learning effect and release times where the objective is to minimize the makespan. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 36 jobs, and the average error percentage of the proposed heuristic is less than 0.11%. 相似文献
5.
We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it
is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines,
that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time
and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two
problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds
of 1.5 and 1.46557 for the second problem.
The authors would like to dedicate this paper to the memory of our colleague and friend Yong He who passed away in August
2005 after struggling with illness.
D. Ye: Research was supported in part by NSFC (10601048). 相似文献
6.
We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b<n, and in the unbounded model, b=∞. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time
(makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time
approximation schemes (PTAS). 相似文献
7.
In this paper, we investigate the semi-online scheduling problem with known maximum job size on two uniform machines with the speed ratio s≥1. The objective is to minimize the makespan. Two algorithms are presented, where the first is optimal for \(1\leq s\leq\sqrt{2}\), and the second is optimal for 1.559≤s≤2 and \(s\ge \frac{3+\sqrt{17}}{2}\). In addition, the improvement on lower bounds is made for \(2. 相似文献
8.
This paper is concerned with a semi-online scheduling problem with combined information on two identical parallel machines to minimize the makespan, where all the jobs have processing times in the interval \([1,\,t]\) \((t\ge 1)\) and the jobs arrive in non-increasing order of their processing times. The objective is to minimize the makespan. For \(t\ge 1\), we obtain a lower bound \(\max _{N=1,2,3,\ldots }\left\{ \min \{\frac{4N+3}{4N+2}\,,\frac{Nt+N+1}{2N+1}\}\right\} \) and show that the competitive ratio of the \(LS\) algorithm achieves the lower bound. 相似文献
9.
10.
Maksim Barketau Erwin Pesch Yakov Shafransky 《Journal of Combinatorial Optimization》2016,31(2):774-785
We consider the following optimization problem. There is a set of \(n\) dedicated jobs that are to be processed on \(m\) parallel machines. The job set is partitioned into subsets and jobs of each subset have a common due date. Processing times of jobs are interconnected and they are the subject of the decision making. The goal is to choose a processing time for each job in a feasible way and to construct a schedule that minimizes the maximum lateness. We show that the problem is NP-hard even if \(m=1\) and that it is NP-hard in the strong sense if \(m\) is a variable. We prove that there is no approximate polynomial algorithm with guaranteed approximation ratio less than 2. We propose an integer linear formulation for the problem and perform experiments. The experiments show that the solutions obtained with CPLEX within the limit of 5 min are on average about 5 % from the optimum value for instances with up to 150 jobs, 16 subsets and 11 machines. Most instances were solved to optimality and the average CPLEX running time was 32 s for these instances. 相似文献
11.
We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents A and B. We are interested in generating all Pareto-optimal schedules for the two criteria: (1) the total completion time of the jobs in A and the maximum cost of the jobs in B, and (2) the maximum cost of the jobs in A and the maximum cost of the jobs in B. We show that all Pareto-optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening. 相似文献
12.
《Omega》2017
We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machines will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo-polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable. 相似文献
13.
This paper addresses no-wait or no-idle flow shop scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting time. A simple linear deterioration function is assumed and some dominating relationships between machines can be satisfied. It is shown that for the problems to minimize makespan or weighted sum of completion time, polynomial algorithms still exist, although these problems are more complicated than the classical ones. When the objective is to minimize maximum lateness or maximum tardiness, the solutions of a classical version may not hold. 相似文献
14.
Journal of Combinatorial Optimization - This paper introduces a new environment of online scheduling in which jobs are scheduled under the non-delayed processing (NDP) constraint, where NDP means... 相似文献
15.
We study an online scheduling problem with rejection on \(m\ge 2\) identical machines, in which we deal with unit size jobs. Each arriving job has a rejection value (a rejection cost or penalty for minimization problems, and a rejection profit for maximization problems) associated with it. A buffer of size \(K\) is available to store \(K\) jobs. A job which is not stored in the buffer must be either assigned to a machine or rejected. Upon the arrival of a new job, the job can be stored in the buffer if there is a free slot (possibly created by evicting other jobs and assigning or rejecting every evicted job). At termination, the buffer must be emptied. We study four variants of the problem, as follows. We study the makespan minimization problem, where the goal is to minimize the sum of the makespan and the penalty of rejected jobs, and the \(\ell _p\) norm minimization problem, where the goal is to minimize the sum of the \(\ell _p\) norm of the vector of machine completion times and the penalty of rejected jobs. We also study two maximization problems, where the goal in the first version is to maximize the sum of the minimum machine load (the cover value of the machines) and the total rejection profit, and in the second version the goal is to maximize a function of the machine completion times (which measures the balance of machine loads) and the total rejection profit. We show that an optimal solution (an exact solution for the offline problem) can always be obtained in this environment, and determine the required buffer size. Specifically, for all four variants we present optimal algorithms with \(K=m-1\) and prove that in each case, using a buffer of size at most \(m-2\) does not allow the design of an optimal algorithm, which makes our algorithms optimal in this respect as well. The lower bounds hold even for the special case where the rejection value is equal for all input jobs. 相似文献
16.
17.
PJ O'Grady 《Omega》1988,16(6)
The problem of sequencing jobs on a machine in a job shop has been approached by a number of researchers and practitioners. One of the most popular methods is to apply a priority rule to the queue at each machine. The authors have previously published details of an approach which sets the priority of a job as a linear combination of the operation times and due date for that job. The coefficients in the linear combination are set by a simulation and search procedure so as to give good performance based on the performance measure specified. This paper extends this approach to include setup time factors. This extended approach is then applied to data from an actual manufacturing system. The extended approach is shown to improve the performance of the manufacturing system in relation to existing techniques. 相似文献
18.
Yaron Leyvand Dvir Shabtay George Steiner Liron Yedidsion 《Journal of Combinatorial Optimization》2010,19(3):347-368
We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted
number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider
four different models for treating the two criteria. We prove that three of these problems are
NP\mathcal{NP}
-hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can
be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three
NP\mathcal{NP}
-hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial
time optimization algorithm, which is converted to a fully polynomial time approximation scheme. 相似文献
19.
Journal of Combinatorial Optimization - This paper considers a class of problems with linear deteriorating jobs. Jobs are released over time and become known to the online scheduler until their... 相似文献