主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

数学季刊 ›› 2006, Vol. 21 ›› Issue (1): 103-109.

主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China

收稿日期:2004-10-23 出版日期:2006-03-30 发布日期:2023-12-25
作者简介:LI Wen-hua(1965-),female,native of Weishi,Henan,an associate professor of Zhengzhou Uni- versity,Ph.D.,engages in scheduling.
基金资助:
Supported by NSF of Henan Province(0211011000)；

Single Machine Scheduling Problem with Release Dates and Two Hierarchical Criteria to Minimize Makespan and Stocking Cost

Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China

Received:2004-10-23 Online:2006-03-30 Published:2023-12-25
About author:LI Wen-hua(1965-),female,native of Weishi,Henan,an associate professor of Zhengzhou Uni- versity,Ph.D.,engages in scheduling.
Supported by:
Supported by NSF of Henan Province(0211011000)；

摘要/Abstract

摘要： In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.

关键词: scheduling;release , dates;hierarchical , criteria

Abstract: In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.

Key words: scheduling;release , dates;hierarchical , criteria

中图分类号:

O223

李文华. 主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题[J]. 数学季刊, 2006, 21(1): 103-109.

Single Machine Scheduling Problem with Release Dates and Two Hierarchical Criteria to Minimize Makespan and Stocking CostLI Wen-hua . Single Machine Scheduling Problem with Release Dates and Two Hierarchical Criteria to Minimize Makespan and Stocking Cost[J]. Chinese Quarterly Journal of Mathematics, 2006, 21(1): 103-109.

[1]	刘讲军, 曲桢, 胡钢. 一类不确定薛定谔基尔霍夫方程解的存在性和集中性 [J]. 数学季刊, 2020, 35(1): 46-55.
[2]	陈荣军, 秦立珍, 唐国春. 可转包的双目标单机排序问题[J]. 数学季刊, 2015, 30(4): 524-531.
[3]	张劲松. 判定广义严格对角占优矩阵的新准则[J]. 数学季刊, 2015, 30(2): 166-171.
[4]	郭瑞, 杜利敏, 王淳. 基于Vague集的最优路径选择方法[J]. 数学季刊, 2015, 30(1): 130-136.
[5]	何程, 林浩, 豆俊梅, 慕运动. 同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题[J]. 数学季刊, 2014, 29(2): 159-166.
[6]	王乐乐, 张昭. 隔离-免疫-治疗模型的双重近似算法[J]. 数学季刊, 2013, 28(1): 99-104.
[7]	张蒙, 宋国华. 具有连续分布偏差变元的双曲型微分方程振动准则的进一步结果[J]. 数学季刊, 2012, 27(1): 145-151.
[8]	张伟鹏, 朱德明. 一类二阶非线性微分方程的区间振动准则[J]. 数学季刊, 2010, 25(4): 500-509.
[9]	王喜平, 陈琼, 徐继军. 有强迫项的二阶半线性微分方程新的区间振动准则[J]. 数学季刊, 2009, 24(2): 223-226.
[10]	田素霞 . 广义严格对象占优矩阵的充分条件[J]. 数学季刊, 2008, 23(3): 397-402.
[11]	田素霞. 广义对角占优矩阵的判定准则[J]. 数学季刊, 2007, 22(1): 63-67.
[12]	申春雪, 张洪奎. 具有强迫项的二阶半线性微分方程的区间振动准则[J]. 数学季刊, 2005, 20(4): 411-417.