恒速处理机的多机Flow shop最小和调度问题的启发式算法分析

本文研究有n个作业需在5个处理机中心进行加工，处理机中心i由l1个恒速机组成的非抢占式多机flow shop调度最小和问题．每个作业有s个工序，每个工序需在对应的处理机中心的任一台机器上加工处理，作业到达前不能加工，所有作业通过处理机中心的路径相同．目标是确定一个作业在每个处理机中心机器上的可行调度序列，使所有作业在最后处理机中心的加权完成时间总和最小化．在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时，通过特殊flow shop调度松弛方法，我们证明该问题在作业数趋于无穷时，一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的．

Heuristic Analysis for Multiprocessor Flow Shop Min-Sum Scheduling Problem with Uniform Machines at Each Stage

Considered the non-preemptive multiprocessor flow shop scheduling problem with release dates,a fixed number of stages s,l; uniform machines at the stage i,a set of n jobs, each job consisting of s operations,each of which can only he processed on a machine at the corresponding stage,a same routing of all jobs on stage 1 through stage s. The aim was to determine a feasible order of the jobs so as to minimize sum of the weighted completion times of all jobs on the machines at final stage. By using special flow shop scheduling relaxation,we showed that when the job processing requirements and the job weights were respectively independently and identically distributed bounded random variables,the heuristic based on weighted shortest mean processing requirement among available job is asymptotically optimal for this problem,as the number of jobs approached infinity.