The Study of Group Scheduling Problems with General Dual-Position-Based Job Processing Times

Scheduling with group technology has been a vivid research area in the past decades. However, group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios. Accord...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the Operations Research Society of China (Internet) 2017-12, Vol.5 (4), p.509-527
Main Authors: Yu, Xian-Yu, Zhou, De-Qun, Zhang, Yu-Lin
Format: Article
Language:English
Subjects:
Aging
Algorithms
Completion time
Complexity
Group technology
Manufacturing
Mathematical analysis
Mathematical logic
Metals
Optimization
Polynomials
Scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Scheduling with group technology has been a vivid research area in the past decades. However, group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios. Accordingly, this paper considers group scheduling problems with a kind of general group variable processing times model, where the actual processing time of each job in group is variable due to the dual effect of both the job position and the group position. The objectives of two types of considered problems are to minimize the makespan and the total completion time, respectively. Based on the decomposition analysis, the mathematical logic analysis and the computational complexity proof, it is obtained that the makespan minimization problem and the total completion time minimization problem are both polynomially solvable under the condition that the group number is constant. For three special cases of considered problems, polynomial solving algorithms with lower computational complexity are proposed.
ISSN:2194-668X
2194-6698
DOI:10.1007/s40305-017-0159-1