具有交货时间的单机作业调度问题的最优解  

Optimal Schedule of Jobs Scheduling on a Single Machine with Delivery Times

作　　者：宋立明[1] 韩卫[2] 

机构地区：[1]唐山学院信息工程系,唐山063020 [2]燕山大学信息科学与工程学院,秦皇岛066004

出　　处：《科学技术与工程》2009年第8期2229-2231,共3页Science Technology and Engineering

摘　　要：基于回溯思想的算法通过系统地搜索解空间可以得到具有交货时间的n个作业的单机作业调度问题的最优解。给出一种改进算法,使得算法的时间复杂度由O(n!)降低到O(nlgn)。The algorithm based on the backtracking method could find an optimal schedule by searching solutions space systematically of n jobs scheduling on a single machine with delivery times.An improved algorithm is given.Its time complexity is decreased to O（nlgn） from O（n!）.

关 键 词：最优解 作业调度 交货时间 

分 类 号：TP391.75[自动化与计算机技术—计算机应用技术]