...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Optimization in Industrial Engineering >Parallel Jobs Scheduling with a Specific Due Date Asemi-definite Relaxation-based Algorithm
【24h】

Parallel Jobs Scheduling with a Specific Due Date Asemi-definite Relaxation-based Algorithm

机译：并行作业调度，具有特定的截止日期基于Asemi-depitate放松的算法

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical conditions can be easily statedfor some simple models, a graph model approach is required when conflicts of processor usage are present. The main decisions and solving steps are as follows, respectively. (i)??????? Converting the scheduling problem to graph model; (ii)????? Dividing jobs into independent sets: in this phase, we propose a semi-definite relaxation algorithm in which we use graph coloring concept; (iii)??? Sequencing the independent sets as a single-machine scheduling in which jobs in such a system arejob sets formed by using a semi-definite relaxation solution and determining the problem as a schedule that minimizes the sum of the tardiness of jobs. In this regard, after grouping the jobs by a semi-definite programming relaxation algorithm, we used the rounding algorithm for graph coloring. We also proposed a variable neighborhood search algorithm for sequencing the obtained job sets in order to minimize the sum of the tardiness. Experimental results show that this methodology is interesting by obtaining good results.
机译：本文考虑了不同版本的并行机器调度问题，其中并行作业在处理后同时要求预先指定的job依赖性机器数。此松弛从一个经典调度假设中止了一个。虽然可以轻松地说明分析条件一些简单的模型，但是当存在处理器使用冲突时，需要图形模型方法。主要决定和解决步骤分别如下。 （一世）？？？？？？？将调度问题转换为图形模型; （ii）?????将工作分成独立集：在此阶段，我们提出了一种半定放松算法，我们使用图形着色概念; （iii）???将独立集排序为单机调度，其中在这种系统中的作业是通过使用半定放松解决方案形成的job组，并将问题确定为最小化作业减少量的时间表。在这方面，在通过半定编程放松算法对作业进行分组后，我们使用了舍入算法进行图着色。我们还提出了一种可变邻域搜索算法，用于排序所获得的作业集，以便最小化迟到的总和。实验结果表明，通过获得良好的效果，这种方法是有趣的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号