同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题

展开
  • School of Science, Henan University of Technology
HE Cheng(1975-), female, native of Shangcheng, Henan, a lecturer of Henan University of Technology, Ph.D., engages in the scheduling theory and its applications.

收稿日期: 2012-05-31

  网络出版日期: 2020-12-01

基金资助

Supported by the National Natural Science Foundation of China(11201121,11101383); Supported by the China Scholarship Council(201309895008); Supported by the 2013GGJS-079; Supported by the 2011B110008;

Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job

Expand
  • School of Science, Henan University of Technology
HE Cheng(1975-), female, native of Shangcheng, Henan, a lecturer of Henan University of Technology, Ph.D., engages in the scheduling theory and its applications.

Received date: 2012-05-31

  Online published: 2020-12-01

Supported by

Supported by the National Natural Science Foundation of China(11201121,11101383); Supported by the China Scholarship Council(201309895008); Supported by the 2013GGJS-079; Supported by the 2011B110008;

摘要

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time. 

本文引用格式

何程, 林浩, 豆俊梅, 慕运动 . 同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题[J]. 数学季刊, 2014 , 29(2) : 159 -166 . DOI: 10.13371/j.cnki.chin.q.j.m.2014.02.001

Abstract

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time. 
文章导航

/