共查询到20条相似文献,搜索用时 0 毫秒
1.
In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration. 相似文献
2.
3.
Scheduling linearly deteriorating jobs on multiple machines 总被引:1,自引:0,他引:1
This paper investigates the scheduling problems in which the job processing times do not remain constant but are increasing linear functions of their starting times. Two deteriorating scheduling models, Model 1 and Model 2, for multiple machines are considered, with the goal being to minimize the makespan. In this paper, we propose an efficient heuristic for Model 1 and prove that the ratio of the makespan obtained by the heuristic to the optimal makespan is bounded. For Model 2, three heuristics, including a probabilistic heuristic, are proposed for minimizing the makespan. Numerical results are provided to show the efficiency of the approaches in this paper. 相似文献
4.
5.
Wenjie Li Zhenkun Zhang Hailing Liu Jinjiang Yuan 《Information Processing Letters》2012,112(12):503-508
This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b with in the unbounded batching and in the bounded batching. Each job J has an equal-length integral processing time , an integral release time , an integral deadline and a real weight . The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When , we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound . This means that the greedy algorithm is of the best possible for . When p is any positive integer, we provide an online algorithm of competitive ratio for both and . This is the first online algorithm for the problem with a constant competitive ratio. 相似文献
6.
求解可重入并行机调度的混合禁忌搜索算法 总被引:1,自引:0,他引:1
为解决带有一台远程服务设备的可重入并行机调度问题,设计了一种混合禁忌搜索算法。针对传统禁忌搜索算法只从单起始点搜索、容易陷入局部最优等缺点,混合禁忌搜索算法设计了一种Restart策略。当传统禁忌搜索算法陷入局部最优时,用Restart策略重新产生初始解以进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。数值实验中将混合禁忌搜索算法与启发式算法CS相比,结果表明该算法具有较高的求解质量,且其计算时间是可接受的。 相似文献
7.
Jan Remy 《Information Processing Letters》2004,91(4):177-182
This paper is devoted to Resource Constrained Scheduling. An instance for this problem is given by a set of n jobs with lengths and weights and a set of m machines with capacities. At every time each machine can run arbitrary many jobs in parallel but the total weight of these jobs must not exceed the capacity of the machine. Furthermore the m machines work in parallel and we wish to find a schedule that minimizes the makespan or the sum of completion times. Thus load balancing on a cluster of servers is a typical application for scheduling under resource constraints. For both measures the problem is -complete even for m=1. We show that the problem is approximable within factors of 2 (makespan) and 14.85 (sum of completion times) for arbitrary m. 相似文献
8.
We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case. 相似文献
9.
We consider the problem of scheduling a maximum profit selection of equal length jobs on m identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p>0. For each job ji, i=1,…,n we are given a release time ri (at which the job becomes known) and a deadline ri+p+δi. If the job is scheduled and completed before the deadline, a profit of wi is earned. 相似文献
10.
与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。 相似文献
11.
12.
13.
We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which case the algorithm pays its rejection penalty, or it can be scheduled preemptively on the machines, in which case it may increase the maximum completion time of any machine in the schedule, also known as the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the total penalty of all rejected jobs. We study two versions of the problem. The first one is the online problem where the jobs arrive unsorted, and the second variant is the semi-online case, where the jobs arrive sorted by a non-increasing order of penalties. We also show that the variant where the jobs arrive sorted by a non-decreasing order of penalties is equivalent to the unsorted one. We design optimal online algorithms for both cases. These algorithms have smaller competitive ratios than the optimal competitive ratio for the more general problem with arbitrary processing times (except for the case of identical machines), but larger competitive ratios than the optimal competitive ratio for preemptive scheduling of unit jobs without rejection. 相似文献
14.
Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays
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/log2
n)-approximation algorithm for m = 2. 相似文献
15.
We consider the problem of scheduling a set of non-preemptable jobs on two identical parallel machines such that the makespan is minimized. Before processing, each job must be loaded on a machine, which takes a given setup time. All these setups have to be done by a single server which can handle at most one job at a time. For this problem, we propose a mixed integer linear programming formulation based on the idea of decomposing a schedule into a set of blocks. We compare the results obtained by the model suggested with known heuristics from the literature. 相似文献
16.
In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions. 相似文献
17.
In this paper, we study a planning and scheduling problem for unrelated parallel machines. There are n jobs that have to be assigned and sequenced on m unrelated parallel machines. Each job has a weight that represents the priority of the corresponding customer order, a given due date, and a release date. An Automated Guided Vehicle is used to transport at maximum Load max jobs into a storage space in front of the machines in a given period of time. We consider t max consecutive periods. We are interested in minimizing the total weighted tardiness of the jobs across the periods. This measure is important when we are interested in a good on-time delivery performance. We present an appropriate mixed integer program. To solve this NP-hard problem, we develop a heuristic methodology based on decomposition and variable neighborhood search (VNS). The proposed approaches are assessed using randomly generated problem instances. We compare them with a simple heuristic based on decomposition and list scheduling using the Apparent Tardiness Cost dispatching rule. The results demonstrate that the heuristic approach based on VNS performs comparably to the mixed integer program while having reasonable solution times and outperforms the simple heuristic and a genetic algorithm (GA) from previous research. 相似文献
18.
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from
start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible
interval. Earlier works developed an optimal off-line algorithm to schedule all the jobs in a given job set and on-line heuristics
to schedule the jobs in a best effort manner. This paper is concerned with how to find a schedule in which the number of jobs
completed in one of their feasible intervals is maximized. We show that the maximization problem is
-hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible
and preemptible jobs. When jobs are non-preemptible, Algorithm Least Earliest Completion Time First (LECF) is shown to have a 2-approximation factor; when jobs are preemptible, Algorithm Least Execution Time First (LEF) is proved being a 3-approximation algorithm. We show that our analysis for the two algorithms are tight. We also evaluate
our algorithms by extensive simulations. Simulation results show that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms in
average. 相似文献
19.
This paper addresses an allocation and sequencing problem motivated by an application in unsupervised automated manufacturing.
There are n independent jobs to be processed by one of m machines or units during a finite unsupervised duration or shift. Each job is characterized by a certain success probability
p
i
, and a reward r
i
which is obtained if the job is successfully carried out. When a job fails during processing, the processing unit is blocked,
and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to
assign and sequence the jobs on the machines so that the expected total reward is maximized. This paper presents the following
results for this problem and some extensions: (i) a polyhedral characterization for the single machine case, (ii) the proof
that the problem is NP-hard even with 2 machines, (iii) approximation results for a round-robin heuristic, (iv) an effective
upper bound. Extensive computational results show the effectiveness of the heuristic and the bound on a large sample of instances. 相似文献
20.
《Computers & Operations Research》2005,32(11):2731-2750
This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families and unequal ready times of the jobs. Given that the problem is NP-hard, we propose two different decomposition approaches. The first approach forms fixed batches, then assigns these batches to the machines using a genetic algorithm (GA), and finally sequences the batches on individual machines. The second approach first assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Dispatching and scheduling rules are used for the batching phase and the sequencing phase of the two approaches. In addition, as part of the second decomposition approach, we develop variations of a time window heuristic based on a decision theory approach for forming and sequencing the batches on a single machine. 相似文献