储泽楠，王庆喜

(安阳工学院 计算机科学与信息工程学院, 河南 安阳 455000)

0 引言

作业车间调度问题(Job-shop scheduling problem, JSP)是一类满足任务配置和顺序约束要求的资源分配的调度问题，具有广泛的应用背景，譬如生产制造、交通规划、邮电通信、大规模集成电路设计等问题.JSP已被证明是一个典型的NP-hard问题[1]，它的求解难度远大于流水线调度问题，针对其算法的研究一直是学术界和工程界共同关注的重要课题.

目前，制造业的竞争日益激烈，制造企业正朝着有不同完工时间和产品要求的多类型、小批量的生产模式发展.如何利用现有的资源，满足加工任务所需的各种约束，使所有的任务能尽量按时完成，即如何有效地解决JSP问题，就成为一个十分现实和迫切的问题[2].

1 Job-shop调度问题描述

Job-shop调度问题描述为：n个工件在m台机器上加工，Oij表示第i个工件在第j台机器上的操作，相应的操作时间Tij为已知，事先给定各工件在各机器上的加工次序，要求确定与技术约束条件相容的各机器上所有工件的加工次序，使加工性能指标达到最优.在Job-shop问题中，通常假定每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断，机器间缓冲区容量为无限.Job-shop调度问题是一类典型的加工调度问题，是许多实际问题的简化模型[2].

关于JSP的求解往往要考虑生产调度实际期望达到的优化指标，问题的目标函数是这些优化指标的抽象表示，JSP模型的目标函数……