预知两种信息带准备时间的平行机半在线排序

本文研究了P2,rj/sum & max/Cmax问题,即预知所有工件加工时间总和sum和最大工件加工时间max的两台处理器的带准备时间的半在线问题,并给出了竞争比为6/5的最优半在线算法.     

考虑共享机器租借费用的在线订单加工策略及竞争分析

探究了拥有两台平行机资源的制造商在共享制造环境下的实时加工调度决策问题。结合租赁外部共享机器的固定成本与可变成本因素，运用在线理论与竞争分析方法构建了平行机调度over-list在线模型，其最小化目标是工件总完工时间与机器租赁总成本之和。针对工件均为单位长度的情形，分析了问题离线最优方案，进而证明了竞争比下界为■,其中，a为固定租赁成本系数，b(0≤b+时，该下界趋于4/3;同时，设计给出了在线策略TS,并证明当a=2时该策略竞争比为4/3;当a≥3时，其竞争比为1.89。     

考虑订单类型的两台平行批处理机在线调度模型研究

探讨了两台平行批处理机的调度决策问题,着重考虑了订单具有不同加工类型、同一批次只能加工相同类型的订单以及机器批容量有限的调度情形。针对订单实时到达且需要立即决策是否接受的实际情景,运用在线理论构建了平行机批调度在线模型。证明了该问题的竞争比下界为2Bw/（1+√Bw）,其中B和w分别表示批容量和单个订单的最大完工收益。进而设计给出了收益阈值算法PT并证明其对于订单具有紧交货期限的情形竞争比为2（1+Bw）/（1+√Bw）;对于非紧交货期限的情形,证明了修正的PT算法具有竞争比为1+2（1+Bw）/（1+√Bw）。     

考虑加工与运输协同调度的单机排序问题

在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由m辆有容量限制的运输工具运送到同一个顾客处,目标是极小化最后一个送到其顾客的工件的到达时间,本文给出了该问题的一个最优算法,并且证明了该算法的最坏情况界为3/2。     

面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

聚类视角下的差异工件平行机批调度问题

从聚类角度研究差异工件批调度这一组合优化问题.论证了差异工件的分批问题实质为一种广义聚类问题,为求解批调度问题提供了一个全新的途径.提出了批的空间浪费比的概念,将最小化批的总加工时间目标变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明.此外,以批的空间浪费比为基...     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

可折旧设备在线租赁的随机性竞争策略

应用在线算法与竞争分析研究在线租赁问题是近年来国内外的一个研究热点.在一般设备在线租赁的基础上,提出了可折旧设备在线租赁问题.针对离线人具有遗忘性竞争对手的特点分别给出了可折旧设备在线租赁在有无利率情形下的随机性竞争策略.基于在线-离线成本比值矩阵分别证明了有无利率下随机性策略的竞争比,说明了折旧因素的引入使得可折旧设...     

大规模集成电路预烧作业中分批排序问题的数学模型

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题。单机分批排序问题就是n个工件在一台机器上加工,要将工件分批,每批最多可以同时加工B个工件,每批的加工时间等于此批工件中的最大的加工时间。Skutella^[8]1998年把平行机排序的P｜｜∑ω_jC_j和R｜｜∑ω_jC_j表述成二次的0-1整数规划,得到一些令人满意的结果;国内罗守成等^[9]、张倩^[10]给出了单机排序问题1｜｜∑ω_jC_j的数学规划表示,对于用数学规划来研究排序问题是一个很有意义的进展。本文首先介绍总完工时间和最小的带权单机分批排序问题1｜B｜∑ω_jC_j,然后将1｜B｜∑ω_jC_j表示成数学规划的形式,并且用数学规划中的对偶理论证明了SPT序是其特殊情况1｜B=1｜∑C_j的最优解。     

基于任务跟踪的在线租赁问题与竞争策略研究

现实经济活动中,有许多租赁融资决策既非纯在线租赁问题也非纯离线租赁问题,而是介于二者之间的具有部分已知信息的在线租赁问题.基于此研究了工作任务总量已知而工作任务进展序列未知的在线设备租赁问题,以租赁工作所需设备的费用最小为优化目标,建立了该问题的基本数学模型,提出了任务跟踪策略,给出并证明了基于这一策略的算法的竞争比.最后,把该在线租赁问题的竞争比与经典的在线租赁问题的竞争比做了比较分析,结果表明在线租赁问题的算法优于经典的在线算法,竞争性能得到了较大的提高.     

An optimal semi-online algorithm for 2-machine scheduling with an availability constraint

This paper considers a problem of semi-online scheduling jobs on two identical parallel machines with objective to minimize the makespan. We assume there is an unavailable period [B,F] on one machine and the largest job processing time P _max? is known in advance. After comparing B with P _max? we consider three cases, and we show a lower bound of the problem are 3/2, 4/3 and \((\sqrt{5}+1)/2\), respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.     

The hierarchical model for load balancing on two machines

Following previous work, we consider the hierarchical load balancing model on two machines of possibly different speeds. We first focus on maximizing the minimum machine load and show that no competitive algorithm exists for this problem. We overcome this barrier in two ways, both related to previously known models. The first one is fractional assignment, where each job can be arbitrarily split between the machines. The second one is a semi-online model where the sum of jobs is known in advance. We design algorithms of best possible competitive ratios for both these cases. Furthermore, we show that the combination of the two models leads to the existence of an optimal algorithm (i.e., an algorithm of competitive ratio 1). This algorithm is clearly optimal for the makespan minimization problem as well. For the latter problem, we consider the fractional assignment model and design an algorithm of best possible competitive ratio for it. This work was submitted as the M.Sc. thesis of the first author.     

Semi-online scheduling on two uniform machines with the known largest size

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s _j the speed of each machine, j=1,2. Assume 0<s ₁≤s ₂, and let s=s ₂/s ₁ be the speed ratio. First, for the speed ratio \(s\in [1,\sqrt{2}]\), we present an optimal semi-online algorithm \(\mathcal{LSMP}\) with the competitive ratio \(\mathrm{max}\{\frac {2(s+1)}{2s+1},s\}\). Second, we present a semi-online algorithm \(\mathcal{HSMP}\). And for \(s\in(\sqrt{2},1+\sqrt{3})\), the competitive ratio of \(\mathcal{HSMP}\) is strictly smaller than that of the online algorithm \(\mathcal{LS}\). Finally, for the speed ratio s≥s ^*≈3.715, we show that the known largest size cannot help us to design a semi-online algorithm with the competitive ratio strictly smaller than that of \(\mathcal{LS}\). Moreover, we show a lower bound for \(s\in(\sqrt{2},s^{*})\).     

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. 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. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.     

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

     

Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times

We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p _i of every job J _i is bounded by an interval [a,α a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs’ processing times, we denote it by semi-online problem. We deal with two semi-online problems.     

Semi-online scheduling with combined information on two identical machines in parallel

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.     

Semi-online scheduling for jobs with release times

In this paper we consider three semi-online scheduling problems for jobs with release times on m identical parallel machines. The worst case performance ratios of the LS algorithm are analyzed. The objective function is to minimize the maximum completion time of all machines, i.e. the makespan. If the job list has a non-decreasing release times, then $2-\frac{1}{m}$ is the tight bound of the worst case performance ratio of the LS algorithm. If the job list has non-increasing processing times, we show that $2-\frac{1}{2m}$ is an upper bound of the worst case performance ratio of the LS algorithm. Furthermore if the job list has non-decreasing release times and the job list has non-increasing processing times we prove that the LS algorithm has worst case performance ratio not greater than $\frac{3}{2} -\frac{1}{2m}$ .     

Online MapReduce processing on two identical parallel machines

In this work we investigate the online over-list MapReduce processing problem on two identical parallel machines, aiming at minimizing the makespan. Jobs are revealed one by one, and each job consists of one map task and one reduce task. The map task can be arbitrarily split and processed on both machines simultaneously, while the reduce task has to be processed on a single machine and it cannot be started unless the map task has been completed. We first show that the general case of the problem reduces to the classical two machine online scheduling model with an optimal competitive ratio of 3/2. For a special case where the map task is at least as long as the reduce task, we prove that no online algorithm can be less than 4/3-competitive. An optimal Greedy algorithm with a matching competitive ratio is proposed as well.     

New results on two-machine flow-shop scheduling with rejection

In this paper, we consider the off-line and on-line two-machine flow-shop scheduling problems with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. For the off-line version, Shabtay and Gasper (Comput Oper Res 39:1087–1096, 2012) showed that this problem is NP-hard and then provided a pseudo-polynomial-time algorithm, two 2-approximation algorithms and a fully polynomial-time approximation scheme. We further study some special cases in this paper. We show that this problem is still NP-hard even when all jobs have the same processing time on one of the machines or all jobs have the same rejection penalty. Furthermore, we also showed that this problem can be solved in polynomialtime algorithm when all jobs satisfy the agreeable condition on their processing times and rejection penalties. For the on-line version without rejection, Chen and Woeginger [in: Du DZ, Pardalos PM (eds.) Minimax and Applications, 1995] showed that the competitive ratio of any determined on-line algorithm is at least 2. We further show that the competitive ratio of any determined on-line algorithm is at least 2 even when all jobs have the same processing time on the first machine. Finally, for the on-line version with rejection, we present a class of on-line algorithms with the best-possible competitive ratio 2.