共查询到20条相似文献,搜索用时 78 毫秒
1.
2.
考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法. 相似文献
3.
本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法. 相似文献
4.
对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法.对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比. 相似文献
5.
6.
7.
近来具有学习效应的机器排序问题收到广泛的关注.对于机器排序中工件的实际加工来说,与工件加工位置有关的学习模型更具有现实性.本文研究了工件加工位置和与已经加工过的工件之和有关的一般学习效应模型.首先证明文献中与位置和已经加工过的工件加工时间之和有关的学习模型是本模型的特殊情形.其次对于单机排序问题我们提出一般解法. 相似文献
8.
9.
研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法. 相似文献
10.
研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS). 相似文献
11.
《European Journal of Operational Research》2005,167(2):297-319
In this paper we study the job shop scheduling problem under the assumption that the jobs have controllable processing times. The fact that the jobs have controllable processing times means that it is possible to reduce the processing time of the jobs by paying a certain cost. We consider two models of controllable processing times: continuous and discrete. For both models we present polynomial time approximation schemes when the number of machines and the number of operations per job are fixed. 相似文献
12.
Mixed integer formulation to minimize makespan in a flow shop with batch processing machines 总被引:1,自引:0,他引:1
Batch processing machines are commonly used in wafer fabrication, kilns, and chambers used for environmental stress screening (ESS). This paper proposes two models to schedule batches of jobs on two machines in a flow shop. A set of jobs with known processing times and sizes has to be grouped, to form batches, in order to be processed on the batch processing machines. The jobs are nonidentical in size. The processing time of a batch is the longest processing time of all the jobs in that batch. Mixed integer formulations are proposed for the flow shop problem when the buffer capacity is unlimited or zero. Numerical examples are presented to demonstrate the application of our model. 相似文献
13.
One of the most important tasks in service and manufacturing systems is how to schedule arriving jobs such that some criteria
will be satisfied. Up to now there have been defined a great variety of scheduling problems as well as corresponding models
and solution approaches. Most models suffer from such more or less restrictive assumptions like single machine, unique processing
times, zero set-up times or a single criterion. On the other hand some classical approaches like linear or dynamic programming
are practicable for small-size problems only. Therefore over the past years we can observe an increasing application of heuristic
search methods. But scheduling problems with multiple machines, forbidden setups and multiple objectives are scarcely considered.
In our paper we apply a Genetic Algorithm to such a problem which was found at a continuous casting plant. Because of the
forbidden setups the probability for a random generated schedule to be feasible is nearly zero. To resolve this problem we
use three kinds of penalties, a global, a local and a combined approach. For performance investigations of these penalty types
we applied our approaches to a real world test instance with 96 jobs, three machines and two objectives. We tested five different
penalty levels with 51 independent runs to evaluate the impact of the penalties. 相似文献
14.
We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if wi=pi for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants. 相似文献
15.
《European Journal of Operational Research》1998,107(2):354-370
Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out. 相似文献
16.
In this paper, we consider the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. Batch processing machines are frequently encountered in many industrial environments such as heat treatment operations in a steel foundry and chemical processes performed in tanks or kilns. Improved Mixed Integer Linear Programming (MILP) models are presented for the flowshop problem with unlimited or zero intermediate storage. An MILP-based heuristic is also developed for the problem. Computational experiments show that the new MILP models can significantly improve the original ones. Also, the heuristic can obtain the optimal solutions for all the test problem instances. 相似文献
17.
《European Journal of Operational Research》2002,139(2):245-261
Flowshop scheduling deals with processing a set of jobs through a set of machines, where all jobs have to pass among machines in the same order. With the exception of minimizing a makespan on two machines, almost all other flowshop problems in a general setup are known to be computationally intractable. In this paper we study special cases of flowshop defined by additional machine dominance constraints. These constraints impose certain relations among the job processing times on different machines and make the studied problems tractable. 相似文献
18.
We consider the problem of scheduling n jobs on m parallel machines. Each job has a deterministic processing time and a weight associated with it. For uniform machines we show that discounted flowtime is minimized by serving jobs preemptively in increasing order of their remaining processing times, assigning the job with the shortest remaining processing time to the fastest available machine. 相似文献
19.
Machine scheduling with resource dependent processing times 总被引:1,自引:0,他引:1
We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume
that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable
resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more
of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated
parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment
problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation
of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with
Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield
a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming
relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing.
We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming
relaxations. 相似文献
20.
《European Journal of Operational Research》1998,107(2):338-353
Discrete–continuous problems of scheduling nonpreemptable jobs on parallel machines are considered. The problems arise e.g. when jobs are assigned to multiple parallel processors driven by a common electric, hydraulic or pneumatic power source. Existing models have assumed job processing rates as a function of the number of jobs currently being processed, or equivalently the number of machines currently in operation. In this paper a more general model is proposed in which processing rates of a job assigned to a machine depend on the amount of a continuous, i.e. continuously divisible resource (e.g. power) allotted to this job at a time. Thus the problem consists of two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to allocate the continuous resource among jobs already sequenced. We provide a comprehensive analysis of the problem. This includes properties of optimal schedules, efficiently (in particular analytically) solvable cases, formulations of the possibly simplest mathematical programming problems for finding optimal schedules in the general case, heuristics and the worst-case analysis. Although our objective function in this paper is to minimize makespan of a set of independent jobs, the presented methodology can be applied to other criteria, precedence-related jobs, and many resource types (apart from, or instead of machines). 相似文献