基于近似算法求解多设备差异批调度问题
pproximation algorithm for scheduling multiple batching machines with non-identical jobs
考虑了一类作业尺寸有差异的批调度问题，加工环境为并行批处理设备。以制造跨度为优化目标，建立了基于整数规划的数学模型；分析了制造跨度最小化问题的计算复杂性，给出问题可行解规模的上下界；然后设计了一种基于LPT规则和Batch First Fit规则的近似算法，证明了算法的时间性能为O(nlogn)，算法在优化制造跨度时的最坏性能比为（8/3 - 2/3m）。
In this paper, the scheduling problem of parallel batch-processing machines with non-identical job sizes is considered. First, the mathematical model of minimizing makespan is given using mixed integer programming method. The computational complexity of the problem and bounds on the number of feasible solutions are analyzed. Then an O(nlogn) time approximation algorithm is designed based on LPT and Batch First Fit heuristics. The worst case ratio of the algorithm is 8/3 - 2/3m.
程八一
计算技术、计算机技术自动化技术、自动化技术设备
批调度差异作业并行设备近似算法
batch schedulingnon-identical jobsparallel machinesapproximation algorithm
程八一.基于近似算法求解多设备差异批调度问题[EB/OL].(2012-02-14)[2025-08-16].http://www.paper.edu.cn/releasepaper/content/201202-385.点此复制
评论