具有期限约束的工作流调度是云计算中一个具有挑战性的问题。结合不同任务调度序列和虚拟机空闲时隙的利用对调度性能的影响，提出一种改进人工蜂群(artificial bee colony, ABC)的云工作流调度方法(PNABC)对该问题求解，目的是满足期限约束条件下降低工作流执行费用和提高虚拟机利用率。在PNABC中，首先在观察蜂搜索阶段引入邻域搜索代替概率搜索选择好的食物源(调度解),避免了PNABC过早陷入局部最优；其次提出一种结合任务子期限和空闲时隙的解码规则将食物源解码为调度解决方案，该规则通过适当延迟任务的执行来提高虚拟机的利用率；最后针对ABC算法随机迭代中存在调度解违背任务优先级关系的情况，设计了一种结合调度解和就绪任务子集的有效任务调度序列生成方法。将PNABC方法应用于不同规模的工作流实例上。实验表明，PNABC方法在满足期限约束、优化工作流执行费用和提高虚拟机利用率方面比对比算法表现更优。