基于滚动变时间窗的重组批处理机调度研究

针对具有等待时间限制和工件动态到达的重组批处理机调度问题,以拖延时间和最小为目标,提出基于滚动变时间窗的三层混合调度算法。该调度算法是应用滚动时域策略,将重组批处理机调度问题分解为许多变时间窗的子问题;每个子问题调度分三层执行：即产生触发并传递参数、重组批及排序、派工并更新参数。通过实时调度仿真平台和CPLEX平台进行实例验证,结果表明基于滚动变时间窗的三层混合调度算法能够在较短计算时间内获得满意优化解。     

释放时间和工期同序的单机连续型批调度问题

本文研究的连续型批处理机调度问题, 是在钢铁工业管坯的加热过程中提出来的. 工件带有释放时间和工期, 工件进入和离开机器是按周期依次进行的. 本文针对单机连续型批调度问题中工件释放时间和工期同序的情况, 分析了极小化最大拖期和拖期工件数等问题的计算复杂性, 证明了两类问题都是强NP-难的. 对于工件的释放时间和加工时间、工期都同序的特殊情况, 分别给出了能够获得对应问题的最优解的多项式算法.     

批处理机上具有两类释放时间的工件集竞争调度问题

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.     

最小化完成时间和加惩罚值和的批调度问题

考虑如下单机并行批调度问题:给定一些工件,每个工件有给定的处理时间以及惩罚值(可以拒绝处理某些工件,惩罚值为拒绝处理工件所付出的代价).给定一个可同时处理多个工件的批处理器.同时处理的工件形成一个批.同一批处理的工件具有相同的开始时间和结束时间,即开始时间加上这一批中所有工件的最大给定处理时间.判断如何选择要处理的工件,给这些工件分批以及给批排序使得目标函数值最小.对目标函数是被处理工件的完成时间之和加上被拒绝工件的惩罚值之和的情况,通过给出一个动态规划算法,证明当批容量为常量时问题是多项式时间可解的.     

传搁时间约束下的运输与批处理机生产协调调度

针对炼钢模铸系统钢锭高温运作的特点,提出带有传搁时间约束的生产前运输与批处理机生产协调的调度问题.工件的加工时间依赖于其传搁时间,每批工件的加工时间为该批工件中加工时间最大值.目标函数为最小化总完工时间与生产费用的线性组合.通过复杂性分析,证明该问题是强NP难解问题.建立混合整数规划模型,基于动态规划提出两种特殊情况的最优算法,设计原问题的启发式算法并进行最坏情况下性能比分析.实验仿真结果验证了所提出启发式算法的有效性与稳定性.     

工件具有不同尺寸单台批处理机的调度问题

n个工件要在一台有高度限制的批处理机上分批进行加工,工件j的加工时间和高度分别为Pj和Sj,批的加工时间为批中加工时间最大的工件的加工时间,每批加工时,机器的剩余量为批处理机的高度与批中工件的高度和之差,目标函数最小化机器空余总量和工件总完成时间,该NP-难问题源于钢铁企业的罩式退火炉调度问题.基于部分工件分批性质,提...     

差异容量平行批机器环境下基于弱选择约束的调度算法

研究动态到达的差异工件在容量不同的平行批处理机环境下,最小化制造跨度的调度问题,并提出一种有效的元启发式算法.给出一个下界以评价算法的性能,针对所构建批的第1个工件的选择提出弱约束标准及两个基于弱约束的首工件选择策略,并引入到蚁群优化算法.最后通过仿真实验将所提出的改进蚁群算法与已有算法和使用传统选择策略的蚁群算法进行比较,实验结果表明,在建批过程中使用首工件弱约束策略和弱约束下工件尺寸大高概率选择策略是有效的,所提算法的搜索性能较其他算法具有明显优势.     

极小化等待时间的热处理批调度模型与PSO解

机加车间的工件动态到达热处理车间后因受到批处理设备合批等的约束不能及时得到加工,基于工件动态到达的热处理车间,以最小化工件等待时间期望为目标,建立批调度模型,根据工件到达时间实现了粒子群算法微粒的编码以及对工件的分批,通过仿真实验得到结论:缩短工件的加工时间,则在热处理车间内,可以减小工件等待时间期望;降低工件数规模,工件会密集到达热处理环节,从而减短工件等待时间;工件的等待时间期望的大小与工件规模数量有关,工件数规模较小时,大尺寸工件的等待时间期望优于小尺寸工件,规模较大时,则相反。最后,对比分析了本文改进的粒子群算法的效果,发现改进的粒子群算法最优。     

两台等级平行机上部分处理时间已知的半在线调度

工作环境为两台处理速度相同的平行机M1,M2,工件具有两种不同的等级gj=1或2,等级gj=1的工件只能在第1台机器上处理,等级gj=2的工件两台机都能处理.已知等级gj=1的工件的处理时间之和,目标是最小化最大完工时间.主要思路为第一台机器预留出等级gj=1的工件的总处理时间,分析过程中只对等级gj=2的工件进行讨论.文章的三种半在线等级调度问题分别为已知最优处理时间,即已知C opt的情况,可得竞争比大于等于4/3,并有竞争比为4/3的半在线算法;已知工件的最大处理时间,可得竞争比大于等于4/3,同样有算法得出竞争比为4/3;对已知最优处理时间和工件最大处理时间的半在线问题,得到竞争比大于等于6/5,并且找到了相应的算法竞争比小于等于6/5.     

恒速机上的MapReduce在线排序算法下界研究

本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小。对|M_j|≥|R_j|的情形,我们证明了任意在线算法的竞争比不小于1+(1/(2s+2)).     

Unbounded parallel-batching scheduling with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a common unbounded parallel-batching machine. The batching machine can process any number of jobs simultaneously in a batch. The processing time of a batch is equal to the maximum processing time of the jobs in the batch. Two main categories of batch processing based on the compatibility of job families or agents are distinguished. In the case where job families are incompatible, jobs from different families cannot be placed in the same processing batch while all jobs can be placed in the same processing batch when job families are compatible. The goal is to find a schedule for all jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent below or at a fixed value Q. Polynomial-time and pseudo-polynomial-time algorithms are provided to solve various combinations of regular objective functions for the scenario in which job families are either incompatible or compatible.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines

We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than 1+(?{m²+4}-m)/21+(\sqrt{m^{2}+4}-m)/2 , where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.     

Minimizing Mean Completion Time in a Batch Processing System

We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to $B$ jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if $B=1$. We focus on the other extreme case $B=+\infty$. Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case.     

极小化加权完工时间和的无界批量机器并行调度问题

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).