The Study of Group Scheduling Problems with General Dual-Position-Based Job Processing Times
- PDF / 514,366 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 157 Views
The Study of Group Scheduling Problems with General Dual-Position-Based Job Processing Times Xian-Yu Yu1
· De-Qun Zhou1 · Yu-Lin Zhang2
Received: 13 October 2016 / Revised: 22 January 2017 / Accepted: 4 March 2017 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2017
Abstract 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.
This paper was supported by the National Natural Science Foundation of China (No. 71573121), China Postdoctoral Science Foundation Funded Project (No. 2016M590453) and the Fundamental Research Funds for the Central Universities (Nos. NS2016080 and NR2016005).
B
Xian-Yu Yu [email protected] De-Qun Zhou [email protected] Yu-Lin Zhang [email protected]
1
College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
2
School of Economics and Management, Southeast University, Nanjing 210096, China
123
X.-Y. Yu et al.
Keywords Group scheduling · Single machine · Dual position based · Computational analysis Mathematics Subject Classification 90B35
1 Introduction In contemporary manufacturing systems, group technology becomes widely used, in which the jobs with similar product requirements are processed as a group. The group technology can help increase the operations efficiency and decrease the requirements on facilities [1]. Scholars have investigated the wide applications of group technology and summarized many advantages of group technology [2–4]. In a manufacturing environment where group technology is used, the jobs with similar production requirements are classified into groups, and there is no machine setup between two consecutively scheduled jobs from the same group while a setup is required between different groups. This important assumption has raised many interests in the study of scheduling theory for group technology manufacturing environment [5,6]. In classical scheduling theory, the job processing times
Data Loading...
