带工作相容约束的单机分批排序问题

数学季刊 ›› 2007, Vol. 22 ›› Issue (4): 597-601.

带工作相容约束的单机分批排序问题

1.Research Center of Fictitious Economy and Management,Nankai University,Tianjin 300071;2. Department of Mathematics,Zhengzhou University,ghengzhou 450052

收稿日期:2004-07-03 出版日期:2007-12-30 发布日期:2023-10-23
作者简介: ZHANG Qun-fa(1976-), male, native of Zhengzhou, Henan, a doctor of Research Center of Fic- titious Economy and Management, Nankai University, engages in fictitious economy; LIN Yi-xun(1937-), male, native of Zhengzhou, Henan, a professor of Zhengzhou University, engages in graph theory and combinatorial optimization;

The Single Machine Parallel Batch Scheduling Problem with Job Compatibility Constraints

1.Research Center of Fictitious Economy and Management,Nankai University,Tianjin 300071;2. Department of Mathematics,Zhengzhou University,ghengzhou 450052

Received:2004-07-03 Online:2007-12-30 Published:2023-10-23
About author: ZHANG Qun-fa(1976-), male, native of Zhengzhou, Henan, a doctor of Research Center of Fic- titious Economy and Management, Nankai University, engages in fictitious economy; LIN Yi-xun(1937-), male, native of Zhengzhou, Henan, a professor of Zhengzhou University, engages in graph theory and combinatorial optimization;

摘要/Abstract

摘要： The single machine parallel batch problem with job compatibility is considered to minimize makespan,where the job compatibility constraints are represented by a graph G.This problem is proved to be NP-hard.And when the graph G is limited to be a general bipartite,a complete bipartite and a complete m-partite graph,these problems are solved in polynomial time respectively.

关键词: scheduling, batching, makespan, compatibility

Abstract: The single machine parallel batch problem with job compatibility is considered to minimize makespan,where the job compatibility constraints are represented by a graph G.This problem is proved to be NP-hard.And when the graph G is limited to be a general bipartite,a complete bipartite and a complete m-partite graph,these problems are solved in polynomial time respectively.

Key words: scheduling, batching, makespan, compatibility

中图分类号:

TP11

张群发, 林诒勋. 带工作相容约束的单机分批排序问题[J]. 数学季刊, 2007, 22(4): 597-601.

[1]	高园, 党佳瑞, 彭娟. 工件有安装时间的无界平行分批排序研究[J]. 数学季刊, 2022, 37(4): 422-429.
[2]	申惠军, 耿志超. 工件允许拆分加工的单机排序问题[J]. 数学季刊, 2022, 37(4): 412-421.
[3]	张利齐, 周松涛, 录岭法. 关于单机双代理可拒绝排序的一个注记[J]. 数学季刊, 2022, 37(4): 394-402.
[4]	贺茹艳, 原晋江, 张源. 关于工件具有多个维护区间最小化总误工量的可中断排序的一个注记[J]. 数学季刊, 2022, 37(4): 331-342.
[5]	孟金涛, 鲁晓旭, 李士生, 周永卫. 具有工件加工时间相容性和可拒绝的单机分批排序[J]. 数学季刊, 2020, 35(3): 320-330.
[6]	林浩, 何程. 关于最小化最大延迟的分批排序问题的一个动态规划算法的注解[J]. 数学季刊, 2018, 33(2): 206-211.
[7]	陈荣军, 秦立珍, 唐国春. 可转包的双目标单机排序问题[J]. 数学季刊, 2015, 30(4): 524-531.
[8]	冯艳玲, 张玉忠, 贾国柱. 基于多客户的工件可转包排序问题[J]. 数学季刊, 2015, 30(3): 330-338.
[9]	许小艳, 慕运动, 郭晓, 郝赟. 基于重新排序时间错位限制下的最小化总完工时间的平行分批排序[J]. 数学季刊, 2015, 30(2): 274-279.
[10]	何程, 林浩, 豆俊梅, 慕运动. 同时最小化具有相等加工时间的最大完工时间和加权总完工时间的序列分批排序问题[J]. 数学季刊, 2014, 29(2): 159-166.
[11]	陈荣军, 唐国春. 平行机的排序与转包[J]. 数学季刊, 2012, 27(4): 590-597.
[12]	刘海军, 郭小江. 关于Wrpp半群上的Lawson偏序[J]. 数学季刊, 2012, 27(1): 139-144.
[13]	慕运动. 两个目标的重新排序问题[J]. 数学季刊, 2009, 24(3): 349-356.
[14]	冯密罗. 单机最优分批排序的结构性质[J]. 数学季刊, 2009, 24(1): 132-137.
[15]	陈友军, 林诒勋. 限位排序的若干结果[J]. 数学季刊, 2008, 23(2): 202-206.