含作业到达时间的同类机调度问题启发式算法  

Heuristics for Uniform Parallel Machine Scheduling with Release Dates

作　　者：李凯[1] 靳鹏[1] 

机构地区：[1]合肥工业大学管理学院,合肥230009

出　　处：《系统工程理论与实践》2007年第10期105-111,共7页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70631003);合肥工业大学科学研究发展基金(071102F)

摘　　要：研究了目标函数是最小化完成时间和的同类机调度问题,其中作业到达时间可能不同.此问题被证明是强NP-hard问题.由于同类机调度是一种重要的平行机调度问题,而最小完成时间和目标是最常见的正则目标之一,因此完成时间和的同类机调度问题在相关研究领域具有非常重要的地位.为此问题建立数学模型,通过对单机和同型机的相应问题研究成果的推广,提出6个启发式算法,给出算例及其计算结果,并通过实验对算法的性能及算法适应的情形进行了分析.This paper considers the problem of uniform parallel machine scheduling with unequal release dates so as to minimize total completion times. This problem is proved to an NP-hard problem. Uniform parallel machine scheduling is an important class of parallel machine scheduling problems. The objective of minimizing total completion times is a familiar regular criterion. We build a mathematics model for this problem, and then propose 6 heuristic algorithms by the way of extending the research results of the corresponding problems in the single machine or identical parallel machine cases. An example and the compute results are given and the performance of the algorithms by experiment is also analyzed,

关 键 词：同类机调度 完成时间和 到达时间 启发式算法 

分 类 号：O223[理学—运筹学与控制论] TP301[理学—数学]