单机批调度问题是最近十几年广泛研究的一个领域。在本文之中,我们首先针对给定n个工件和一个容量为B的单机并行批处理机器问题展开研究。每个工件Jj(j∈{1,2,…,n})具有一些给定属性(rj,pj,sizej,wj),j是工件Jj能够被调度的最早时间,即到达时间；Pj是工件Jj在不被打断情况下,需要在机器上处理的时间,即处理时间；sizej是工件Jj的尺寸；wj是工件Jj在被拒绝情况下需要在目标中付出的惩罚值。机器能够把一定数量的工件作为一批同时进行处理,只要这批工件的尺寸总和不超过B。一批的处理时间等于这批中工件的最大处理时间。同一批处理的工件具有相同的起始时间和相同的完成时间。我们的目标是调度这些工件,使得接受工件的最大完成时间与拒绝工件的惩罚总值之和最小。我们首先给出了此类问题无论到达时间是否相同均是NP-困难的,且不存在近似比小于3／2的近似算法；之后,我们给出了工件具有相同到达时间的情况的2-近似算法；最后我们给出了工件可能具有不同到达时间的问题的2+∈-近似算法,其中∈>0可以为任意小的常数。另外,受实时机器视觉系统启发,我们对并行批混合流水车间最小化最大完成时间的调度问题进行遗传算法的研究。此问题描述如下：工件集J中的n个工件需要被k-阶段的流水车间处理,其中每个阶段i(i∈{1,2,…,k})有mi个平行批处理器。设Bip表示阶段i(i∈{1,2,…,k})的处理器p(p∈{1,2,….mi})的容量。也就是说,在阶段i的处理器p至多同时处理Bip个工件。一批的处理时间等于这批工件中的最大处理时间。我们可以把一个工件看成一个具有k个任务的序列,每个任务针对一个阶段,且任何任务必须在其前序任务处理完成之后才能够被处理。设Pij为工件Jj(Jj∈J)在阶段i(i∈{1,2,…,k})需要的处理时间。我们对此问题有以下的假定：1.每个阶段的处理器只能处理此阶段的任务；2.同一处理器在一个时刻只能处理一批。设Cij(S)为调度S中工件Jj(Jj∈J)的第i(i∈(1,2,…,k})个任务的完成时间。我们问题的目标可以简化为找出最小化maXJj∈J{Ckj(S)}的调度S。我们分别对交叉操作和变异操作给出两种不同的方法,然后对这些方法的四种不同的组合方式进行实验。在此基础之上,我们还针对工件具有尺寸和可以拒绝的最小化最大完成时间加惩罚总值之和的单机并行批调度问题,给出一种新的解码方法和四个版本的遗传算法,最后得到一个版本的遗传算法好于其他三个等实验结果。