Makespan minimization scheduling with ready times, group technology and shortening job processing times. (2nd February 2018) - Wang, Ji-Bo; Liu, Lu; Wang, Jian-Jun; Li, Lin
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.