Makespan minimization scheduling with ready times, group technology and shortening job processing times. (2nd February 2018)

• Record Type: Journal Article
• Authors: Wang, Ji-Bo; Liu, Lu; Wang, Jian-Jun; Li, Lin
• Editors: Berenbrink, Petra
• Is Part Of: Computer journal. Volume 61:Number 9(2018)
• Page Start: 1422
• Page End: 1428
• Publication Date: 2018-02-02
• Subjects: scheduling -- group technology -- shortening job processing times -- ready time; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy007
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: We investigate a group scheduling problem with shortening job processing times on a single machine in which the shortening is proportional-linear shortening and the setup time of a group is fixed. For the maximum completion time (i.e. the makespan) minimization problem with ready times, we show that the general case of the problem can be solved in polynomial time if the number of groups is a given constant. We also prove that some special cases of the problem can be optimally solved by a lower order algorithm respectively.