Abstract: In the network parallel computing system, the problem which aims to schedule tasks with multiprocessor and multistage is common. Hence, this paper proposes the model of Multiprocessor Task Job-shop Scheduling Problem, i.e. MTJSP, a combination of Multiprocessor Task Scheduling（MTS） and Job-shop Scheduling Problem（JSP）. MTJSP in which every task needs more than one stage to complete is different from the classical MTS in which there is only one stage for each task. The mathematic formulation of MTJSP is constructed and a Hybrid Particle Warm Optimization（HPSO） is designed for solving it which includes the decoding schemes, new ways for particle updating, memories for better solutions and function of local searching. Plenty of instances are used to measure the performance of HPSO and numerical results show that HPSO behaves very well on instances of both JSP and MTJSP.

Key words: multiprocessor task, Job-shop Scheduling Problem（JSP）, Particle Swarm Optimization（PSO）, local search

摘要： 在网络并行计算系统中，具有多处理机任务需求的多步骤调度是一类常见问题，为此提出一种混合了多处理机任务调度（Multiprocessor Task Scheduling，MTS）和作业车间调度（Job-shop Scheduling Problem，JSP）的调度模型，即多处理机任务作业车间调度（Multiprocessor Task Job-shop Scheduling Problem，MTJSP）。与传统MTS不同的是MTJSP的每项任务的完成都要经历多个步骤。首先对[m]台处理机加工[n]项任务的MTJSP调度问题建立数学模型，然后设计了一种混合粒子群优化（Hybrid Particle Swarm Optimization，HPSO）算法进行求解。算法的改进工作包括：设计出针对多处理机问题的解码策略；采用新的粒子更新方式；增加记忆库功能，以保证全局最优解的多样性；加入基于模拟退火的局部搜索功能。大量的仿真实验验证HPSO的性能，结果显示HPSO不但能够有效解决MTJSP问题，在求解经典JSP问题中也表现优良。

关键词: 多处理机任务, 作业车间调度, 粒子群优化算法, 局部搜索