A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraints

Many multi-stage processes employ programmed transporters to move jobs between stages and impose time windows on the starting times of the material handling operations. The operations are typically cyclic and, in each cycle, a given set of operations must be performed. The problem is to determine the sequence and the timing of the operations so that the cycle time is minimized, while the time windows and the transporter traveling time constraints are satisfied. This paper introduces a new sequence-dependent parameter, called the minimal time span, that gives a tight lower bound on the cycle time for a candidate schedule. A search procedure based on this parameter is proposed. This procedure requires only simple calculations (addition and subtraction) at each non-leaf node. Computational experience is reported. With all the benchmark problems, the number of nodes visited during the resulting search process is no more than the number of linear programming problems solved in previous studies reported in the literature. With all the randomly generated test problems, the lower bound achieved by the proposed procedure is close to that achieved by the linear programming based approach. We also show that, if a condition regarding the processing time constraints is satisfied, the use of this minimal time span parameter leads to a direct solution to the associated linear programming problem for a candidate schedule.