A two-stage stochastic programming for single yard crane scheduling with uncertain release times of retrieval tasks

Nowadays maritime transportation has become the mainstream of the global logistics, and the operational efficiency of container terminals plays a critical role in maritime transportation. As one of the most important terminal operational issues, yard crane scheduling that handles both storage and retrieval tasks has caught a lot of interest. However, the uncertainty on the release times of retrieval tasks, as one common phenomenon in daily operations, has been ignored in the literature. This paper investigates single yard crane scheduling to minimise the expected total tardiness of tasks, and focus on the case with uncertain release times of retrieval tasks. A two-stage stochastic programming model is proposed, and the sample average approximation (SAA) approach is applied to solve small instances of the problem. For large-scale instances, a genetic algorithm (GA) and a rule-based heuristic are developed. To evaluate the performances of the solution methods, numerical experiments with 300 instances are implemented. Computational results show that the rule-based heuristic outperforms both GA and SAA in terms of solution quality and running time.     

Single machine scheduling problem with stochastic sequence-dependent setup times

In this study, we consider stochastic single machine scheduling problem. We assume that setup times are both sequence dependent and uncertain while processing times and due dates are deterministic. In the literature, most of the studies consider the uncertainty on processing times or due dates. However, in the real-world applications (i.e. plastic moulding industry, appliance assembly, etc.), it is common to see varying setup times due to labour or setup tools availability. In order to cover this fact in machine scheduling, we set our objective as to minimise the total expected tardiness under uncertain sequence-dependent setup times. For the solution of this NP-hard problem, several heuristics and some dynamic programming algorithms have been developed. However, none of these approaches provide an exact solution for the problem. In this study, a two-stage stochastic-programming method is utilised for the optimal solution of the problem. In addition, a Genetic Algorithm approach is proposed to solve the large-size problems approximately. Finally, the results of the stochastic approach are compared with the deterministic one to demonstrate the value of the stochastic solution.     

Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry

This study examines a two-stage two-dimensional cutting stock problem encountered by a paper mill company. The problem includes various machine-related and operational constraints based on real-world situations. Paper products are manufactured using two major cutting processes. Each cutting machine has a specific minimum and maximum width for input and output rolls and is limited by the maximum number of rolls it can cut at the same time. A mathematical model is presented to formally address the problem and an efficient multiple-choice knapsack-based heuristic algorithm is proposed to solve the problem. To demonstrate the efficiency of the proposed heuristic algorithm, computational experiments are conducted on test data-set generated from real-world data provided by a large paper mill company in the Republic of Korea.     

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.     

A heuristic algorithm for master production scheduling problem with controllable processing times and scenario-based demands

Master production scheduling (MPS) is widely used by manufacturing industries in order to handle the production scheduling decisions in the production planning hierarchy. The classical approach to MPS assumes infinite capacity, fixed (i.e. non-controllable) processing times and a single pre-determined scenario for the demand forecasts. However, the deterministic optimisation approaches are sometimes not suitable for addressing the real-world problems with high uncertainty and flexibility. Accordingly, in this paper, we propose a new practical model for designing an optimal MPS for the environments in which processing times may be controllable by allocating resources such as facilities, energy or manpower. Due to the NP-hardness of our model, an efficient heuristic algorithm using local search technique and theory of constraints is developed and analysed. The computational results especially for large-sized test problems show that the average optimality gap of proposed algorithm is four times lower than that of exact solution using GAMS while it consumes also significantly smaller run times. Also, the analysis of computational results confirms that considering the controllable processing times may improve the solution space and help to more efficiently utilise the available resources. According to the model structure and performance of the algorithm, it may be proposed for solving large and complex real-world problems particularly the machining and steel industries.     

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.     

Heuristic approaches for mixed-model sequencing problem with stochastic processing times

Despite many pioneering efforts and works over the past decades, stochastic events have not been studied extensively in mixed-model assembly lines thus far. For a mixed-model sequencing problem with stochastic processing times, this paper aims to minimise expected total work overload. It also focuses on the most critical workstation of the line. In practice, this assumption is useful when the whole or a big portion of the assembly line is considered as a single station. In order to tackle the problem, a dynamic programming (DP) algorithm as well as two greedy heuristics from the literature is employed. However, it is realised that the DP cannot guarantee the optimal sequence neither for stochastic nor deterministic problems. It is because the calculation of work overload is involved in a recursive procedure that affects the states’ value functions. Therefore, by the use of network representation, the problem is modelled as a shortest path problem and a new heuristic, inspired by Dijkstra’s algorithm is developed to deal with it. Numerical results show that the proposed method outperforms other algorithms strongly. Finally, some discussion is provided about why one should consider stochastic parameters and why the proposed heuristic performs well in this regard.     

An improved heuristic approach for multi-objective facility layout problem

Multi-objective facility layout problem (mFLP) generates a different layout by varying objectives weights. Since the selection of objective weights in mFLP is critical, stages of designing layout having multiple objectives, the objective weights therefore play an important role in the layout design of mFLP. In practice, it is selected randomly by the layout designer based on his/her past experience that restricts the layout designing process completely designer dependent and thus the layout varies from designer to designer. This paper aims to resolve the issues of selecting the objective weight for each objective. We propose four methods to determine objective weight which makes the design process of mFLP completely designer independent.     

Heuristic solution to the product targeting problem based on mathematical programming

Maintaining customer lifetime longevity is a crucial issue for companies. One of the strategies for dealing with this issue is to offer different promotion campaigns. Planning these campaigns creates a problem: Which targeted products in the campaign should be offered to which customers in order to maximise profit? This problem becomes vitally important under the conditions of a limited budget and a lower bound on sales target of each product. It is also remarkable from the operational research perspective because of its NP-hardness. In this study, heuristic approaches to the product targeting problem based on mathematical programming are suggested. The proposed approaches principally determine the products to be included in a campaign using heuristic rules and then distribute these products to the customers optimally. Computational results confirm that these approaches generate superior solutions to the problem in comparison with existing methods in the literature. The effectiveness and efficiency of the approaches are also shown on very large-sized test problems generated in order to verify their potential for practical applications.     

Hybrid branch and bound algorithms for the two-stage assembly scheduling problem with separated setup times

This article proposes hybrid branch and bound algorithms to minimise the makespan for the two-stage assembly scheduling problem with separated setup times. In the studied problem, there are multiple machines at the first stage, each of which produces a component of a job. When all components are available, a single assembly machine at the second stage completes the job. Existing algorithms are based on the state space search and hence suffer from the state space explosion problem. In order to reduce the search space, lower and upper bounds for a partial schedule are proposed. Also, a heuristic function and a dominance rule are developed to guide the search process. Moreover, accelerated factors are introduced to increase the speed of the search. Experimental results indicate that our algorithms outperform an existing method, and can find the optimal or near-optimal schedules in a short time for all tested problems with up to ten thousand jobs and nine first-stage machines.     

A hybrid heuristic for the multiple choice multidimensional knapsack problem

In this article, a new solution approach for the multiple choice multidimensional knapsack problem is described. The problem is a variant of the multidimensional knapsack problem where items are divided into classes, and exactly one item per class has to be chosen. Both problems are NP-hard. However, the multiple choice multidimensional knapsack problem appears to be more difficult to solve in part because of its choice constraints. Many real applications lead to very large scale multiple choice multidimensional knapsack problems that can hardly be addressed using exact algorithms. A new hybrid heuristic is proposed that embeds several new procedures for this problem. The approach is based on the resolution of linear programming relaxations of the problem and reduced problems that are obtained by fixing some variables of the problem. The solutions of these problems are used to update the global lower and upper bounds for the optimal solution value. A new strategy for defining the reduced problems is explored, together with a new family of cuts and a reformulation procedure that is used at each iteration to improve the performance of the heuristic. An extensive set of computational experiments is reported for benchmark instances from the literature and for a large set of hard instances generated randomly. The results show that the approach outperforms other state-of-the-art methods described so far, providing the best known solution for a significant number of benchmark instances.     

Synchronisation of scarce resources for a parallel machine lotsizing problem

In this paper we present a novel approach to tackling the synchronisation of a secondary resource in lot-sizing and scheduling problems. This kind of problem occurs in various manufacturing processes (e.g. wafer testing in the semiconductor industry, production and bottling of soft drinks). We consider a scenario of parallel unrelated machines that have to be equipped with a tool or need a special kind of resource for processing. Our approach allows tracing the assignment of these secondary resources across different machines and synchronising their usage independently of the time period. We present extensions of the general lot-sizing and scheduling problem and of the capacitated lot-sizing problem. We prove that the latter model is a special case of the first, but it performs computationally much better.     

A simple heuristic for perishable item inventory control under non-stationary stochastic demand

In this paper, we study the single-item single-stocking location non-stationary stochastic lot sizing problem for a perishable product. We consider fixed and proportional ordering cost, holding cost and penalty cost. The item features a limited shelf life, therefore we also take into account a variable cost of disposal. We derive exact analytical expressions to determine the expected value of the inventory of different ages. We also discuss a good approximation for the case in which the shelf-life is limited. To tackle this problem, we introduce two new heuristics that extend Silver’s heuristic and compare them to an optimal Stochastic Dynamic Programming policy in the context of a numerical study. Our results demonstrate the effectiveness of our approach.     

A new distribution-free model for disassembly line balancing problem with stochastic task processing times

Effective conduct with End of Life (EOL) products is a hot research topic in green and smart manufacturing. For EOL product recycling and remanufacturing, a fundamental problem is to design an efficient disassembly line under consideration of stochastic task processing times. This problem focuses on selecting alternative task processes, determining the number of opened workstations, and assigning operational tasks to the workstations. The goal is to minimise the total cost consisting of workstation operational cost and hazardous component processing cost. Most existing works assume that the probability distribution of task processing times can be estimated, however, it is often not likely to access the complete probability distribution due to various difficulties. Therefore, this study investigates disassembly line design with the assumption that only the mean, standard deviation and an upper bound of task processing times are known. Our main contributions include: (i) a new decomposition color graph is proposed to intuitively describe all possible processes, (ii) a new distribution-free model is proposed, and (iii) some problem properties are established to solve the model. Experimental results show that the distribution-free model can effectively deal with stochastic task processing times without given probability distributions.     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Hedge against total flow time uncertainty of the uniform parallel machine scheduling problem with interval data

We consider a total flow time minimisation problem of uniform parallel machine scheduling when job processing times are only known to be bounded within certain given intervals. A minmax regret model is proposed to identify a robust schedule that minimises the maximum deviation from the optimal total flow time over all possible realisations of the job processing times. To solve this problem, we first prove that the maximal regret for any schedule can be obtained in polynomial time. Then, we derive a mixed-integer linear programming (MILP) formulation of our problem by exploiting its structural properties. To reduce the computational time, we further transform our problem into a robust single-machine scheduling problem and derive another MILP formulation with fewer variables and constraints. Moreover, we prove that the optimal schedule under the midpoint scenario is a 2-approximation for our minmax regret problem. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

Simulation-based optimisation approach for the stochastic two-echelon logistics problem

This work proposes a simulation-based optimisation approach for the two-echelon vehicle routing problem with stochastic demands (2E-VRPSD). In the proposed 2E-VRPSD, freight delivery from the depot to the customers is managed by shipping the freight through intermediate satellites, while each customer has a stochastic demand. The 2E-VRPSD is an extension of the famous capacitated vehicle routing problem with stochastic demands and the two-echelon vehicle routing problem (2E-VRP). A tabu search algorithm is designed to solve the 2E-VRPSD, in which Monte Carlo sampling is adopted to tackle the issue of stochastic demands. Modified two-echelon vehicle routing problem benchmark instances are used in the numerical experiments. The computational results show the advantage of the proposed simulation-based approach.     

A Lagrangian heuristic for minimising risk using multiple heterogeneous metrology tools

Motivated by the high investment and operational metrology cost, and subsequently the limited metrology capacity, in modern semiconductor manufacturing facilities, we model and solve the problem of optimally assigning the capacity of several imperfect metrology tools to minimise the risk in terms of expected product loss on heterogeneous production machines. In this paper, metrology tools can differ in terms of reliability and speed. The resulting problem can be reduced to a variant of the Generalized Assignment Problem (GAP), the Multiple Choice, Multiple Knapsack Problem (MCMKP). A Lagrangian heuristic, including multiple feasibility heuristics, is proposed to solve the problem that are tested on randomly generated instances.     

Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times

In this paper, a genetic algorithm (GA) with local search is proposed for the unrelated parallel machine scheduling problem with the objective of minimising the maximum completion time (makespan). We propose a simple chromosome structure consisting of random key numbers in a hybrid genetic-local search algorithm. Random key numbers are frequently used in GAs but create additional difficulties when hybrid factors are implemented in a local search. The best chromosome of each generation is improved using a local search during the algorithm, but the better job sequence (which might appear during the local search operation) must be adapted to the chromosome that will be used in each successive generation. Determining the genes (and the data in the genes) that would be exchanged is the challenge of using random numbers. We have developed an algorithm that satisfies the adaptation of local search results into the GAs with a minimum relocation operation of the genes’ random key numbers – this is the main contribution of the paper. A new hybrid approach is tested on a set of problems taken from the literature, and the computational results validate the effectiveness of the proposed algorithm.