THE EFFECT OF RANDOM PROCESSING TIMES ON FLOW SHOP SCHEDULING WITH CONSTANT WORK-IN-PROCESS

This article presents a study based on optimization and simulation, which considers Permutation Flow Shop Problem (PFSP). In general, PFSP studies assume deterministic times and unlimited buffers. In this work, we consider PFSP with work-in-process (WiP) limit and random processing times. The objective is to analyze the effect of the randomness of processing times and the WiP limit on two performance measures: makespan and mean flow time. The computational method consists of generating instances, determining the sequences that minimize these two key performances and, finally, simulating the optimal sequences considering random processing times and limits for WiP levels. The instances were generated considering two-line sizes (3 and 5 machines) and the number of jobs equal to five and ten times the number of machines. We have a total of 240 scheduling problems (four configurations – m x n, thirty instances of each configuration, two performance measures). To solve the scheduling problem, we decided for an exact method that generated optimal or quasi-optimal solutions with reasonable computational times. In this way, two models of Mixed Integer Linear Programming (MILP) were formulated. All 240 scheduling instances were run, assuming an optimality gap of 1%. The model provides as the solution the start times and the performance measure of the optimal sequence, which will be simulated. The Discrete Event Simulation (DES) model has of two processes: i) release of jobs to the line, ii) processing jobs on the line. In the first process, the simulation controls the release according to the WiP, allowing the entry of a new job whenever the line occupancy is lower than its work-in-process capacity (WiP Cap). In-line processing follows the standard tandem queues simulation with the first-come-first-served rule (FCFS). With the simulation model, each of the 240 outputs from the optimization step was simulated with 2500 replications to estimate the makespan and the mean flow time, under different conditions of variability and WiP Cap. The results confirms that the WiP limit and the randomness of the times affect the makespan and the mean flow time, as expected, with the variance effect being lower than the WiP limit. Of course, the relaxed problem (i.e., unlimited buffers) has makespan and mean flow times values smaller, but we know that, from a practical perspective, it is necessary to limit the work-in-process. Our work shows that setting a WiP Cap/m=2 makes it possible to control the level of WiP in the line, without significant losses in performance, since the indicators are close to the value corresponding to the no control case. Considering the effect of the variance, the higher the coefficient of variation, the higher (worse) the values of the makespan and the mean flow time. Nevertheless, the effect, although negative, is small.