批处理机上具有两类释放时间的工件集竞争调度问题

摘要：

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.

关键词：调度、竞争工件集合、释放时间、批处理机

所属期刊栏目：46

资助基金：国家自然科学基金项目;辽宁省科技厅自然科学基金计划重点项目;沈阳市科技计划项目

在线出版日期：2020-04-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：168-177