目前,很多学者都在尝试用不同的方法来求解Job-Shop调度问题。但是由于Job-Shop调度问题本身的复杂性,每种方法都存在着不足之处,如方法比较复杂或解的近优性较差。借鉴操作系统中进程(线程)调度算法的先进思想,设计一个新的相对简洁的方法来求解Job-Shop调度问题的算法。Job-Shop调度问题中的工序具有并发行、异步性等特点。因此,充分利用资源(机器)并且发挥工序的特点可以提高加工效率,缩短总的加工时间。首先对Job-Shop调度问题进行建模,将单作业映射为加工树;然后,借鉴操作系统中进程(线程)调度的先进思想,根据加工树上的层来设置工序的优先级;将工序分为不可调度工序、准可调度工序和可调度工序,并动态的生成备选工序集;除了在工序需要动态调整的情况外,在调度过程中始终遵循着机器忙原则,即尽可能的让机器不停的工作。调度工序时,从备选工序集中选择工序,然后调度到机器上进行加工。选择工序需要遵循四个调度策略,即优先级策略、短用时策略、长路经策略和动态调整策略。成功调度一个工序后,从加工树上删除工序节点,再根据加工树重新生成备选工序集。当备选工序集为空时表明作业加工完毕。同时,以根对齐方式将多个作业或动态加入的作业构造成一棵虚拟加工树的方法,从而简化了Job-Shop调度问题。对于多作业Job-Shop调度问题或动态Job-Shop调度问题,调度时按照本文设计的四种调度策略调度虚拟加工树。通过实例验证、比较,算法具有令人满意的算法复杂度,而且近优效果好。因此,算法具有一定的理论和现实意义。