Research On Hybrid Robust Scheduling For Flow Shop Under Uncertainty

Production scheduling occupies a crucial strategic position in production management. Research on production scheduling problems can greatly increase production efficiency, thereby enhance market competitiveness. Production scheduling problems have been intensively studied during the last several decades. Flow shop scheduling of great complexity is a classical model of production scheduling. It is an ideal simplified model of practical production line scheduling problem. Flow shop scheduling problem has been widely used in discrete manufacturing industry as well as process industry. Therefore, studies on flow shop scheduling have both great theoretical significance and engineering value.Previous research on production scheduling problems has been mostly focused on static and deterministic environments, in which all problem information is known in advance. However, in the real word, production shops are dynamic and uncertain. Myriad unforeseen disturbances, such as rush orders, uncertainty of processing times, unavailable materials and machine breakdowns etc, will arise during practical production processes. Uncertainty typically leads to deviations from predetermined schedule, even make it infeasible. All these situations require rescheduling of the initially allocated jobs. Therefore, in dynamic environments, considering the influence of uncertainties can not only help generate high quality and stability schedules, but also improve business efficiency and customer satisfaction.This dissertation investigates flow shop scheduling problem under different uncertainties. Summarily, the main research work of this dissertation lies in two aspects as follows.Partial rescheduling for flow shop scheduling subject to an earlier unforeseen machine. We discusses a permutation flow shop scheduling problem with efficiency and stability as bi-criterion, where an unforeseen breakdown may happen in a machine during the execution of a long initial schedule. The objective of efficiency is the makespan and the objective of stability is measured by the total schedule deviation of the new schedule to the initial schedule. A partial rescheduling procedure is developed for the permutation flow-shop scheduling problem, where how to identify a partial rescheduling window is a difficulty to handle. A detailed procedure to identify a partial rescheduling window is presented and a local rescheduling sub-problem is established based on the partial rescheduling window. A local objective function of the rescheduling sub-problem derives from the combination of the efficiency for the sub-problem and the total delay of unfinished jobs due to breakdown. An extensive experiment was conducted to compare the partial rescheduling procedure and the right-shift rescheduling procedure. Computational results show that the partial rescheduling can provide a reasonable trade-off between solution quality and computational efforts and greatly improve stability of schedules with little sacrifice in efficiency.Hybrid robust scheduling for flow shop scheduling with an uncertain new arrival job. A new hybrid robust scheduling approach is presented to handle flow shop scheduling problem in the presence of an uncertain new arrival job, which the firm must compete with other firms to win. The approach includes two main steps. In the first step, the predictive schedule is created by inserting additional idle time into the original schedule to absorb the impacts of uncertainty. In the predictive schedule, we must determine the amount of additional idle time for uncertain job and its position in the schedule. In the second step, the uncertain job may arrive in a machine during the execution of the predictive schedule. A new rescheduling procedure is adopted to accommodates the newly arriving job, which forms the rescheduling domain by absorbing idle time in the predictive schedule. The objective of efficiency and stability will be considered during the rescheduling sub-problem. Extensive simulation experiments show the effectiveness of hybrid robust scheduling.