Ye, H., Li, W., & Nault, B. R. (2020). Trade-off balancing between maximum and total completion times for no-wait flow shop production. International Journal of Production Research, 58(11), 3235-3251. doi: 10.1080/00207543.2019.1630777  PDF (last version of working paper)

We propose a trade-off balancing (TOB) heuristic in a no-wait flow shop to minimise the weighted sum of maximum completion time (Cmax) and total completion time (TCT) based on machine idle times. We introduce a factorization scheme to construct the initial sequence based on current and future idle times at the operational level. In addition, we propose a novel estimation method to establish the mathematical relationship between the objectives min(Cmax) and min(T CT ) at the production line level. To evaluate the performance of the TOB heuristic, computational experiments are conducted on the classic Taillard’s benchmark and one-year historical data from University of Kentucky HealthCare (UKHC). The computational results show that minimisations of Cmax and TCT yield inconsistent scheduling sequences, and these two sequences are relatively uncorrelated. We also show that our TOB heuristic performs better than the best existing heuristics with the same computational complexity and generates stable performances in balancing trade-offs.

Li, W., Nault, B. R., & Ye, H. (2019). Trade-off balancing in scheduling for flow shop production and perioperative processes. European Journal of Operational Research, 273(3), 817-830. doi: 10.1016/j.ejor.2018.08.048 PDF (last version of working paper)

We balance trade-offs between two fundamental and possibly inconsistent objectives, minimization of maximum completion time and minimization of total completion time, in scheduling serial processes. We use a novel approach of current and future deviations (CFD) to model the trade-offs between the two completion times. We also use weights α and β to balance trade-offs at the operation level and at the process level, respectively. Accordingly, we develop a constructive CFD heuristic, and compare its performance with three leading constructive heuristics in scheduling based on three separate datasets: 5400 small-scale instances, 120 Taillard’s benchmark instances, and one-year historical records of operating room scheduling in a university hospital system. We show that minimization of maximum completion time and minimization of total completion time yield inconsistent scheduling sequences, and the two sequences are relatively uncorrelated. We also show that our CFD heuristic can balance trade-offs between these two objectives, outperform the three leading heuristics across different performance measures, and allow larger variations on two fundamental completion times. This means that trade-off balancing by our CFD heuristic enables a serial process to have a larger tolerance on variations of process performance, and keeps the process better under control. This performance improvement can be significant for flow shop scheduling in manufacturing in trading-off production and holding costs, and for operating room scheduling across the perioperative process in healthcare in trading-off hospital cost and patient waiting time.

Ye, H., Li, W., Abedini, A., & Nault, B. (2017). An effective and efficient heuristic for no-wait flow shop production to minimize total completion time. Computers & Industrial Engineering, 108, 57-69. doi: 10.1016/j.cie.2017.04.002 PDF  (last version of working paper)

No-wait flow shop production has been widely applied in manufacturing. However, minimization of total completion time for no-wait flow shop production is NP-complete. Consequently, achieving good effectiveness and efficiency is a challenge in no-wait flow shop scheduling, where effectiveness means the deviation from optimal solutions and efficiency means the computational complexity or computation time. We propose a current and future idle time (CFI) constructive heuristic for no-wait flow shop scheduling to minimize total completion time. To improve effectiveness, we take current idle times and future idle times into consideration and use the insertion and neighborhood exchanging techniques. To improve efficiency, we introduce an objective increment method and determine the number of iterations to reduce the computation time. Compared with three recently developed heuristics, our CFI heuristic can achieve greater effectiveness in less computation time based on Taillard′s benchmarks and 600 randomly generated instances. Moreover, using our CFI heuristic for operating room (OR) scheduling, we decrease the average patient flow times by 11.2% over historical ones in University of Kentucky Health Care (UKHC).