排序的贪婪算法的参数上界

本文研究平行机排序中最著名的贪婪算法─LPT算法的性质．经典排序中机器随时可以开始加工．本文研究机器不都是从开始就可以加工,而是需要一个准备时间,也就是说本文研究各台机器最早可以开工的时间可以不同的同型号平行机（ideaticalParallel）的排序问题,分析LPT算法得到的近似解的参数上界．     

机器排序的几个问题及结果

本文以生产计划中的能力受限单机排序问题、加工过程中产品可以拆分到不同机器上加工的平行机排序问题和基于ＪＩＴ生产哲理的平行机排序问题为主，按能力受限单机排序问题、正则目标函数平行机排序问题变形和非正则目标函数平行机排序问题，介绍它们的模型和最近的几个理论研究结果．同时提出有待研究的问题．     

可拆分有调整时间的平行机排序问题的一个算法

考虑有独立调整时间的同型号平行机排序问题,极小化最迟完工时间,产品允许拆分,同一产品被拆分后各部分可以在不同机器上同时加工,该问题是ＮＰ－ｈａｒｄ问题。本文首先给出该问题的一个启发式算法ＭＬ,然后证明了其最坏情况估计不超过７／４－１／ｍ（ｍ≥２）。     

机器具有准备时间的双目标平行机排序问题

本文讨论机器具有准备时间的双目标平行机排序问题，目标函数为完工时间和最优条件下极小化最大完工时间．通过对SPT排序的性质的分析，给出了最优排序的下界．在此基础上证明了SPT排序的误差界为3／2，并且是紧界．     

两台机器及时完工工件数最大化问题的近似算法

平行机排序问题Pm／／∑uj当m≥2时是一个NP—难的问题．本文利用求解1／／∑uj的Moore算法构造了与P2／／∑uj等价的P2／／n-∑uj问题的一个多项式时间近似算法，并征明了该算法的绝对性能比为3／4．此外还研究了机器带有准备时间的问题P2，ri／／n-∑uj，并证明了在这种情况下算法的渐近性能为2／3。     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

带约束的平行机排序的一个近似算法

讨论有资源约束和有机器准备时间的平行机排序问题,资源约束为每个机器至多可加工k个工件,在极小化makespan的上给出了一个匹配算法,证明其最坏情况最紧界是2-m^-1,并进一步给出了它的两个带参数的最坏情况界。     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

异时排序问题的算法复杂性

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时,该问题等价于图上的最大匹配问题,因此存在组合强多项式时间算法;但量当机器台数为3或者多于3时,该问题是强NP困难的．     

Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.     

On a methodology for discrete–continuous scheduling

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).     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

Interval Scheduling on identical machines

Interval Scheduling problems (IS) address the situation where jobs with fixed start and fixed end times are to be processed on parallel identical machines. The optimization criteria of interest are the maximization of the number of jobs completed and, in case weights are associated with jobs, the subset of jobs with maximal total weight. We present polynomial solutions to several IS problems and study computational complexity issues in the situation where bounds are imposed on the total operating time of the machines. With this constraint, we show that tractability is achieved again when job preemption is allowed.     

On the machine scheduling problem with job delivery coordination

This paper examines two scheduling problems with job delivery coordination, in which each job demands different amount of storage space during transportation. For the first problem, in which jobs are processed on a single machine and delivered by one vehicle to a customer, we present a best possible approximation algorithm with a worst-case ratio arbitrarily close to 3/2. For the second problem, which differs from the first problem in that jobs are processed by two parallel machines, we give an improved algorithm with a worst-case ratio 5/3.     

Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes

This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3 m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives.     

带服务器的三台平行机排序问题的复杂性和近似算法

讨论带有两具服务器的三台机的平行机排序问题,在这个问题的实例中,每一个工件都有一个时间长度 安装操作必须要由服务器来完成,每一个服务器在同一时刻只能安装一个工件,用三段式描述表示此问题即为Ｐ３,Ｓ２／ｓｉ＝１／Ｃｍａｘ,证明了此问题为ＮＰ－Ｃ的,分别给出了在在线和离线条件下的近似算法,并且估计了算法的最坏情况界。     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

On unit time open shops with additional restrictions

We consider open shop problems with unit processing times,n jobs have to be processed onm machines. The order in which a given job is processed on the machines is not fixed. For each job a release time or a due date may be given. Additional, we consider the restriction that every machine must perform all corresponding operations without any delay time. Unit time open shop problems with release times to minimize total completion time were unsolved up to now for both allowed and forbidden delay times. We will solve these problems in the case of two and three machines. Furthermore we will give polynomial algorithms for several no-delay-problems with due dates.