Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

A hierarchical approach for the capacitated lot-sizing and scheduling problem with a special structure of sequence-dependent setups

This research deals with the single machine multi-product capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup times and setup costs. The CLSP determines the production quantities and the sequence to satisfy deterministic and dynamic demand during multiple periods. The objective is to minimise the total sum of the inventory holding costs and the sequence-dependent setup costs. We consider a special form of sequence-dependent setup times where the larger product we produce next, the more setup time we need. As a solution approach, we propose a two-level hierarchical method consisting of upper-level planning and the lower-level planning. In the upper-level planning, we solve the lot-sizing problem with estimated sequence-independent setup times utilising the characteristic of the special structure of setup times. Then we solve the scheduling problem in the lower-level planning. The proposed method is compared with the single-level optimal CLSP solution and an existing heuristic developed for the uniform structure of setup times.     

Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness

This paper addresses the NP-hard problem of scheduling N independent jobs on a single machine with release dates, due dates, sequence dependent setup times, and no preemption where the objective is to minimize the weighted sum of squared tardiness. A Lagrangian relaxation based approach is developed for single-machine scheduling with sequence dependent setup times that is based on a list scheduling concept in conjunction with Lagrangian relaxation. Sequence dependent setup times are formulated as capacity constraints, and then are relaxed using Lagrangian multipliers. The primal problem is decomposed into job-level subproblems which are solved optimally and an approximate dual problem is then solved using a sub-gradient technique. The result of the relaxation is a list of jobs sequenced by beginning times that is then improved via a three-way swap. Experimental results are compared with EDD (Earliest Due Date) and ATCS (Apparent Tardiness Cost with Setups) dispatching rules, a four-way swap local search, tabu search, and simulated annealing. The adopted approach results in superior solution quality with respect to EED, ATCS, four-way swap, and tabu search results. It has comparable solution quality to the simulated annealing results, but is substantially more computationally efficient. Overall, the approach is capable of dealing with realistically sized single machine scheduling problems with release dates, due dates, and sequence dependent setup times.     

Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan

A wide range of uncertainties exists in some real-world production environments which result in uncertain setup and/or processing times. Factors such as crew skills, shortages in equipment and resource breakdowns can be the sources of these uncertainties. This study considers a two-machine production flowshop scheduling problem where both setup and processing times are treated as uncertain variables. The objective is to minimise makespan which is an effective way of resource utilisation. There exists a dominance relation in the literature for the two-machine flowshop scheduling problem with uncertain setup and processing times. However, the dominance relation has not been evaluated. In this study, we evaluate the existing dominance relation. Moreover, a new dominance relation is established and shown to be more effective than the existing one. Furthermore, twenty-five implementations of a polynomial time algorithm are developed. Extensive computational experiments are conducted to evaluate the performance of the implementations of the algorithm. The computational experiments indicate that the overall gap (error) of the best implementation of the algorithm is less than 0.3% when compared to the optimal solution. Moreover, the performance of this implementation of the algorithm is the best one when compared to the remaining implementations for all the considered experimental environments. Additionally, the performance of this implementation of the algorithm is shown to be insensitive to the uncertainty in setup times.     

Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem

Scheduling-Location (ScheLoc) problem is a new and interesting topic in manufacturing, considering location and scheduling decisions simultaneously. Most existing works focus on the deterministic problems. In practice, however, job-processing times are usually uncertain due to some factors. This paper investigates the stochastic parallel machine ScheLoc problem to minimise the weighted sum of the location cost and the expectation of the total completion time. A two-stage stochastic programming formulation is proposed, then the sample average approximation (SAA) method is adapted to solve the small-size problems. To efficiently address the large-scale problems, a genetic algorithm (GA) and a scenario-based heuristic are designed. Numerical experiments on 450 instances are conducted. Computational results show that the scenario-based heuristic outperforms SAA method and GA in terms of solution quality and computational time.     

Minimizing the total machine workload for the wafer probing scheduling problem

The Wafer Probing Scheduling Problem (WPSP) is a practical generalization of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the Integrated Circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we consider the WPSP and formulate the WPSP as an integer programming problem to minimize the total machine workload. We demonstrate the applicability of the integer programming model by solving a real-world example taken from a wafer probing shop floor in an IC manufacturing factory.     

Scenario-based multi-objective robust scheduling for a semiconductor production line

Scheduling problems of semiconductor manufacturing systems (SMS) with the goal of optimising some classical performance indices (NP-hard), tend to be increasingly complicated due to stochastic uncertainties. This paper targets the robust scheduling problem of an SMS with uncertain processing times. A three-stage multi-objective robust optimisation (MORO) approach is proposed, that can collaboratively optimise the performance indices and their robustness measures. In the first stage, this paper studies the scheduling problem in the deterministic environment and obtains feasible scheduling strategies that perform well in four performance indices (the average cycle time (CT), the on-time delivery rate (ODR), the throughput (TP), and the total movement amount of wafers (MOV)). Then, in the second stage, the uncertainties are introduced into the production system. In the third stage, this paper proposes a hybrid method consisting of scenario planning, discrete simulation, and multi-objective optimisation to obtain an approximately and more robust optimal solution from the feasible scheduling strategy set. The proposed MORO approach is tested in a semiconductor experiment production line and makes a full analysis to illustrate the effectiveness of our method. The results show that our MORO is superior concerning the total robustness with multi-objective.     

Bi-criteria SDST hybrid flow shop scheduling with learning effect of setup times: water flow-like algorithm approach

In studies on automatic scheduling problems, processing times do not differ according to repetition of job or process sequences so it may also be necessary to consider processing times independent from setup times. While considering setup times, the human factor has an important effect on setup, so by the processing of similar tasks frequently worker skills improve and they are able to perform setup at a greater pace. This fact is known as the ‘learning effect’ in the literature. This paper deals with sequence-dependent setup times (SDSTs) hybrid flow shop scheduling with learning effect of setup times for minimising weighted sum of makespan and total tardiness. A mathematical programming model that incorporates these aspects of the problem is developed which belongs to the NP-hard class. Thus, because of the intensive computation, we propose a novel meta-heuristic approach called water flow-like algorithm (WFA) which has the feature of multiple and dynamic numbers of solution agents. Various parameters of the problem and the WFA are reviewed by means of Taguchi experimental design. For the evaluation of the proposed WFA, problem data was generated to compare it against a random key genetic algorithm (RKGA). The results demonstrate the high performance of the WFA with respect to the RKGA.     

Multiple machine JIT scheduling: a tabu search approach

This paper presents an approach to solving the multiple machine, non-preemptive, earliness-tardiness scheduling problem with unequal due dates in a flow shop with machine tiers (FMT). In this variant of the flow shop problem, machines are arranged in tiers or groups, and the jobs must visit one machine in each tier. The processing times, machine assignments, and due dates are deterministic and known in advance. The objective is to find a permutation schedule that minimizes the total deviation of each job from its due date. A tabu search (TS) meta-heuristic combined with an LP evaluation function is applied to solve this problem and results are compared to optimal permutation solutions for small problems and the earliest due date schedule for large problems. Several neighborhood generation methods and two diversification strategies are examined to determine their effect on solution quality. Results show that the TS method works well for this problem. TS found the optimal solution in all but one of the small problem instances and improved the earliest due date solutions for larger instances where no optimal solutions could be found.     

Probabilistic asymptotic analysis of stochastic online scheduling problems

In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper we consider the objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate, and processing requirements are bounded and identical and independently distributed across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem, flow shop problem, and uniform parallel machine problem. Our simulation studies of these stochastic online scheduling problems show that two generic nondelay algorithms perform very well as long as the number of jobs is larger than 100.     

The burn-in test scheduling problem with batch dependent processing time and sequence dependent setup time

The burn-in test scheduling problem (BTSP) is a variation of the complex batch processing machine scheduling problem, which is also a generalisation of the liquid crystal injection scheduling problem with incompatible product families and classical identical parallel machine problem. In the case we investigated on the BTSP, the jobs are clustered by their product families. The product families can be clustered by different product groups. In the same product group, jobs with different product families can be processed as a batch. The batch processing time is dependent on the longest processing time of those jobs in that batch. Setup times between two consecutive batches of different product groups on the same batch machine are sequentially dependent. In addition, the unequal ready times are considered in the BTSP which involves the decisions of batch formation and batch scheduling in order to minimise the total machine workload without violating due dates and the limited machine capacity restrictions. Since the BTSP involves constraints on unequal ready time, batch dependent processing time, and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with compatible product families or incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Consequently, this paper proposes a mixed integer programming model to solve the BTSP exactly. In addition, two efficient solution procedures which solve the BTSP are also presented.     

Robust makespan minimisation in identical parallel machine scheduling problem with interval data

Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min–max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

Robust disassembly line balancing with ambiguous task processing times

Disassembly line balancing problem (DLBP), which is to select disassembly process, open workstations and assign selected tasks to opened workstations, plays an important role in the recycling of End Of Life products. In real-world disassembly operations, task processing times are usually stochastic due to various factors. Most related works address the uncertain processing times by assuming that the probability distribution is known and the task processing times are independent of each other. In practice, however, it is difficult to get the complete distributional information and there is always underlying correlation between the uncertain processing times. This paper investigates the DLBP with partial uncertain knowledge, i.e. the mean and covariance matrix of task processing times. A new distributionally robust formulation with a joint chance constraint is proposed. To solve the problem, an approximated mixed integer second-order cone programming (MI-SOCP) model is proposed, and a two-stage parameter-adjusting heuristic is further developed. Numerical experiments are conducted, to evaluate the performance of the proposed method. We also draw some managerial insights and consider an extension problem.     

A new approach to solving stochastic programming problems with recourse

A new numerical approach to the solution of two-stage stochastic linear programming problems is described and evaluated. The approach avoids the solution of the first-stage problem and uses the underlying deterministic problem to generate a sequence of values of the first-stage variables which lead to successive improvements of the objective function towards the optimal policy. The model is evaluated using an example in which randomness is described by two correlated factors. The dynamics of these factors are described by stochastic processes simulated using lattice techniques. In this way, discrete distributions of the random parameters are assembled. The solutions obtained with the new iterative procedure are compared with solutions obtained with a deterministic equivalent linear programming problem. It is concluded that they are almost identical. However, the computational effort required for the new approach is negligible compared with that needed for the deterministic equivalent problem.     

Single-machine stochastic scheduling with dual criteria

In this note we consider a single-machine scheduling problem where job processing times and due dates are random variables with known distributions. The objective of the problem is to find a sequence of the jobs such that a secondary criterion is minimized subject to a primary criterion being held at its best value. Three different models dealing with various primary and secondary criteria are analyzed in the paper. We provide algorithms to solve the problems optimally.     

Forecasting policies for scheduling a stochastic due date job shop

This work studies the problem of scheduling a production plant subject to uncertain processing times that may arise, e.g. from the variability of human labour or the possibility of machine breakdowns. The problem is modelled as a job shop with random processing times, where the expected total weighted tardiness must be minimized. A heuristic is proposed that amplifies the expected processing times by a selected factor, which are used as input for a deterministic scheduling algorithm. The quality of a particular solution is measured using a risk averse penalty function combining the expected deviation and the worst case deviation from the optimal schedule. Computational tests show that the technique improves the performance of the deterministic algorithm by 25% when compared with using the unscaled expected processing times as inputs.     

β-Robust scheduling for single-machine systems with uncertain processing times

In scheduling environments with processing time uncertainty, system performance is determined by both the sequence in which jobs are ordered and the actual processing times of jobs. For these situations, the risk of achieving substandard system performance can be an important measure of scheduling effectiveness. To hedge this risk requires an explicit consideration of both the mean and the variance of system performance associated with alternative schedules, and motivates a β-robustness objective to capture the likelihood that a schedule yields actual performance no worse than a given target level. In this paper we focus on β-robust scheduling issues in single-stage production environments with uncertain processing times. We define a general β-robust scheduling objective, formulate the β-robust scheduling problem that results when job processing times are independent random variables and the performance measure of interest is the total flow time across all jobs, establish problem complexity, and develop exact and heuristic solution approaches. We then extend the 0-robust scheduling model to consider situations where the uncertainty associated with individual job processing times can be selectively controlled through resource allocation. Computational results are reported to demonstrate the efficiency and effectiveness of the solution procedures.     

An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns

Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. Furthermore, most scheduling problems that have been discussed in the literature are under the assumption that machines are continuously available. Nevertheless, in most real-life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to scheduled preventive maintenance where the periods of unavailability are known in advance (deterministic unavailability). This paper deals with hybrid flow shop scheduling problems in which there are sequence-dependent setup times (SDSTs), and machines suffer stochastic breakdowns, to optimise objectives based on the expected makespan. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA) can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. In this research, a computational method based on a clonal selection principle and an affinity maturation mechanism of the immune response is used. This paper describes how we can incorporate simulation into an immune algorithm for the scheduling of a SDST hybrid flow shop with machines that suffer stochastic breakdowns. The results obtained are analysed using a Taguchi experimental design.     

Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times

In this paper, a fuzzy bi-objective mixed-integer linear programming (FBOMILP) model is presented. FBOMILP encompasses the minimisation workload imbalance and total tardiness simultaneously as a bi-objective formulation for an unrelated parallel machine scheduling problem. To make the proposed model more practical, sequence-dependent setup times, machine eligibility restrictions and release dates are also considered. Moreover, the inherent uncertainty of processing times, release dates, setup times and due dates are taken into account and modelled by fuzzy numbers. In order to solve the model for small-scale problems, a two-stage fuzzy approach is proposed. Nevertheless, since the problem belongs to the class of NP-hard problems, the proposed model is solved by two meta-heuristic algorithms, namely fuzzy multi-objective particle swarm optimisation (FMOPSO) and fuzzy non-dominated sorting genetic algorithm (FNSGA-II) for solving large-scale instances. Subsequently, through setting up various numerical examples, the performances of the two mentioned algorithms are compared. When α?=?0.5 (α is a level of risk-taking and when it increases the decision-maker’s risk-taking decreases), FNSGA-II is fairly more effective than FMOPSO and has better performance especially in solving large-sized problems. However, when α rises, it can be stated that FMOPSO moderately becomes more appropriate. Finally, directions for future studies are suggested and conclusion remarks are drawn.     

An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times

In this paper, we consider a simplified real-life identical parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize makespan. We propose a heuristic to solve this problem. Our method is composed of two parts. The problem is first reduced into a single machine scheduling problem with sequence-dependent setup times. This reduced problem can be transformed into a Traveling Salesman Problem (TSP), which can be efficiently solved using Little's method. In the second part, a feasible initial solution to the original problem is obtained by exploiting the results of the first part. This initial solution is then improved in a step by step manner, taking into account the setup times and job splitting. We develop a lower bound and evaluate the performances of our heuristic on a large number of randomly generated instances. The solution given by our heuristic is less than 4.88% from the lower bound.