可拆分平行机排序问题研究

平行机排序问题是把n个产品安排到m台机器上加工，使其总费用最小．通常的平行机排序问题都假设（C1）：任何产品不能在不同机器上同时加工．但是，如果把产品的加工时间看成一个产品量的需求，就可以假设（C2）：允许同一产品拆分在不同机器上同时加工．本文首先回顾了C1假设下平行机排序问题已有的结果，然后基于假设C2，讨论了各种费用目标下问题的算法及其复杂性．在没有生产准备时间的情况下，给出了一些问题的多项式算法和线性规划方法．在有独立生产准备时间的情况下，给出了P／split／Cmax问题的启发式算法及其算法分析．     

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

带单服务器的自由作业排序问题的启发式算法

研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).     

带有装卸服务器的两台平行机调度问题的LS和LPT算法

研究带有一个装载服务器和一个卸载服务器的两台平行机调度问题.每个工件在加工前必须由装载服务器安装到机器上,加工结束后由卸载服务器从机器上进行卸载.装载和卸载时间均为单位时间,目标是极小化最大完工时间.该问题是NP难问题,文章主要分析LS和LPT两个经典的启发式算法,分别证明了这两个算法的紧界为11/7和7/6改进了已有结果.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

考虑成本的最大延迟时间同类机调度问题

假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

加工时间依赖于机器的自由作业排序问题

1992年M．Dror提出工件的加工时间依赖于机器的排序问题（schedulingwithmachinedependentprocessingtimes），并研究以最大完工时间（makespan）和以总的完工时间为优化目标的两种这类排序问题．然而，M．Dror对以总的完工时间为优化目标提出的“最优算法”是错误的．本文用算例表明他提出的算法不是最优的，并在机器连续加工的条件下，把这个排序问题转化成指派问题（assignmentproblem），从而可以用匈牙利算法得到最优解．最后，我们提出几个尚未解决的问题，以期引起国内外同行进一步研究．     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

关于最小化最大延迟的分批排序问题的一个动态规划算法的注解（英文）

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n~2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.     

On scheduling an unbounded batch machine

A batch machine is a machine that can process up to c jobs simultaneously as a batch, and the processing time of the batch is equal to the longest processing time of the jobs assigned to it. In this paper, we deal with the complexity of scheduling an unbounded batch machine, i.e., c=+∞. We prove that minimizing total tardiness is binary NP-hard, which has been an open problem in the literature. Also, we establish the pseudopolynomial solvability of the unbounded batch machine scheduling problem with job release dates and any regular objective. This is distinct from the bounded batch machine and the classical single machine scheduling problems, most of which with different release dates are unary NP-hard. Combined with the existing results, this paper provides a nearly complete mapping of the complexity of scheduling an unbounded batch machine.     

Scheduling a single machine with multiple job processing ability to minimize makespan

This paper investigates a new problem, called single machine scheduling with multiple job processing ability, which is derived from the production of the continuous walking beaming reheating furnace in iron and steel industry. In this problem, there is no batch and the jobs enter and leave the machine one by one and continuously, which is different from general single machine batch scheduling problem where the jobs in a batch share the same start and departure time. Therefore, the start time and the departure time of a job depend on not only the job sequence but also the machine capacity. This problem is also different from the single semi-continuous batching machine scheduling recently studied in the literature, where the jobs are processed in batch mode and a new batch cannot be started for processing until the processing of the previous batch is completed though jobs in the same batch enter and leave the machine one by one. The objective of this problem is to minimize the makespan. We formulate this problem as a mixed integer linear programming model and propose a particle swarm optimization (PSO) algorithm for this problem. Computational results on randomly generated instances show that the proposed PSO algorithm is effective.     

Scheduling on a Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases.     

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum cost and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

Minimizing number of tardy jobs on a batch processing machine with incompatible job families

In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure.     

Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. Jobs have release dates. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases. Relating scheduling theory and graph theory appears to be an interesting and important concept.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.