Hybrid simulated annealing and MIP-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system

This paper addresses lot sizing and scheduling problem of a flow shop system with capacity constraints, sequence-dependent setups, uncertain processing times and uncertain multi-product and multi-period demand. The evolution of the uncertain parameters is modeled by means of probability distributions and chance-constrained programming (CCP) theory. A new mixed-integer programming (MIP) model with big bucket time approach is proposed to formulate the problem. Due to the complexity of problem, two MIP-based heuristics with rolling horizon framework named non-permutation heuristic (NPH) and permutation heuristic (PH) have been performed to solve this model. Also, a hybrid meta-heuristic based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling is developed to solve the problem. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristic and select the optimal levels of the algorithm’s performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the hybrid meta-heuristic against exact solution algorithm and heuristics.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.     

Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach

This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.     

Dynamic uncapacitated lot sizing with random demand under a fillrate constraint

This paper deals with the single-item dynamic uncapacitated lot sizing problem with random demand. We propose a model based on the “static uncertainty” strategy of Bookbinder and Tan (1988). In contrast to these authors, we use exact expressions for the inventory costs and we apply a fillrate constraint. We present an exact solution method and modify several well-known dynamic lot sizing heuristics such that they can be applied for the case of dynamic stochastic demands. A numerical experiment shows that there are significant differences in the performance of the heuristics whereat the ranking of the heuristics is different from that reported for the case of deterministic demand.     

考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。     

Carryover sequence-dependent group scheduling with the integration of internal and external setup times

This paper addresses a group scheduling problem in a two-machine flow shop with a bicriteria objective and carryover sequence-dependent setup times. This special type of group scheduling problem typically arises in the assembly of printed circuit boards (PCBs). The objective is to sequence all board types in a board group as well as board groups themselves in a way that the objective function is minimized. We introduce the carryover sequence-dependent setup on machines, and call it internal setup. As an opportunity for manufacturers to decrease the costs, the focus is to completely eliminate the role of the kitting staff. Thus, we introduce the external setup (kitting) time for the next board group and require it to be performed by the machine operator during the time he is idle. Consequently, the internal and external setup times are integrated in this research, and to the best of our knowledge it is for the first time a research on PCB group scheduling is performed by integrating both setups. In order to solve this problem, first a mathematical model is developed. Then a heuristic together with two other meta-heuristic algorithms (one based on tabu search and the other based on genetic algorithm) are proposed and their efficiency and effectiveness on several problems are tested. Also a statistical experimental design is performed in order to evaluate the impact of different factors on the performance of the algorithms.     

Modeling lotsizing and scheduling problems with sequence dependent setups

Several production environments require simultaneous planing of sizing and scheduling of sequences of production lots. Integration of sequencing decisions in lotsizing and scheduling problems has received an increased attention from the research community due to its inherent applicability to real world problems. A two-dimensional classification framework is proposed to survey and classify the main modeling approaches to integrate sequencing decisions in discrete time lotsizing and scheduling models. The Asymmetric Traveling Salesman Problem can be an important source of ideas to develop more efficient models and methods to this problem. Following this research line, we also present a new formulation for the problem using commodity flow based subtour elimination constraints. Computational experiments are conducted to assess the performance of the various models, in terms of running times and upper bounds, when solving real-word size instances.     

Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company

The aim of this work is to propose a solution approach for a capacitated lot sizing and scheduling real problem with parallel machines and shared buffers, arising in a packaging company producing yoghurt. The problem has been formulated as a hybrid Continuous Set-up and Capacitated Lot Sizing Problem (CSLP–CLSP). A new effective two stage optimisation heuristic based on the decomposition of the problem into a lot sizing problem and a scheduling problem has been developed. An assignment of mixture to buffers is made in the first stage, and therefore the corresponding orders are scheduled on the production lines by performing a local search. Computational tests have been performed on the real data provided by the company. The heuristic exhibits near-optimal solutions, all obtained in a very short computational time.     

Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

A global MILP model for FMS scheduling

Flexible manufacturing systems (FMS) require intelligent scheduling strategies to achieve their principal benefit — combining high flexibility with high productivity. A mixed-integer linear programming model (MILP) is presented here for FMS scheduling. The model takes a global view of the problem and specifically takes into account constraints on storage and transportation. Both of these constrained resources are critical for practical FMS scheduling problems and are difficult to model. The MILP model is explained and justified and its complexity is discussed. Two heuristic procedures are developed, based on an analysis of the global MILP model. Computational results are presented comparing the performance of the different solution strategies. The development of iterative global heuristics based on mathematical programming formulations is advocated for a wide class of FMS scheduling problems.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

Mathematical programming based heuristics for the 0–1 MIP: a survey

The 0–1 mixed integer programming problem is used for modeling many combinatorial problems, ranging from logical design to scheduling and routing as well as encompassing graph theory models for resource allocation and financial planning. This paper provides a survey of heuristics based on mathematical programming for solving 0–1 mixed integer programs (MIP). More precisely, we focus on the stand-alone heuristics for 0–1 MIP as well as those heuristics that use linear programming techniques or solve a series of linear programming models or reduced problems, deduced from the initial one, in order to produce a high quality solution of a considered problem. Our emphasis will be on how mathematical programming techniques can be used for approximate problem solving, rather than on comparing performances of heuristics.     

Some insights into proportional lot sizing and scheduling

This paper deals with proportional lot sizing and scheduling (PLSP) and gives some insights into the properties of this problem. Such insights may be useful for developing heuristic and/or exact solution procedures. The emphasis of this paper is on the multi-level, multi-machine case. We provide a mixed-integer programming model, relate it to other models that can be found in the literature, and discuss characteristics which make solving instances of the PLSP-model a hard task.     

A Neural Network Application in Personnel Scheduling

In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems.     

Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process

We consider a scheduling problem in a factory producing printed circuit boards (PCBs). The PCB assembly process in this factory can be regarded as a flowshop which has two special characteristics: jobs have sequence dependent setup times and each job consists of a lot (batch) of identical PCBs. Because of the latter characteristic, it is possible to start a job on a following machine before the job is entirely completed on a previous machine, that is, there is time-lag between machines. In this paper, we propose several heuristics, including taboo search (TS) and simulated annealing (SA) methods, for this generalized flowshop scheduling problem with the objective of minimizing mean tardiness. We compare suggested heuristics after series of tests to find appropriate values for parameters needed for the two search algorithms, TS and SA. Results of computational tests on randomly generated test problems are reported.     

Integrated exact,hybrid and metaheuristic learning methods for confidentiality protection

A vital task facing government agencies and commercial organizations that report data is to represent the data in a meaningful way and simultaneously to protect the confidentiality of critical components of this data. The challenge is to organize and disseminate data in a form that prevents such critical components from being inferred by groups bent on corporate espionage, to gain competitive advantages, or having a desire to penetrate the security of the information underlying the data. Controlled tabular adjustment is a recently developed approach for protecting sensitive information by imposing a special form of statistical disclosure limitation on tabular data. The underlying model gives rise to a mixed integer linear programming problem involving both continuous and discrete (zero-one) variables. We develop stratified ordered (s-ordered) heuristics and a new meta-heuristic learning approach for solving this model, and compare their performance to previous heuristics and to an exact algorithm embodied in the state-of-the-art ILOG- CPLEX software. Our new approaches are based on partitioning the problem into its discrete and continuous components, first creating an s-ordered heuristic that reduces the number of binary variables through a grouping procedure that combines an exact mathematical programming model with constructive heuristics. To gain further advantages we then replace the mathematical programming model with an evolutionary scatter search approach that makes it possible to extend the method to large problems with over 9000 entries. Finally, we introduce a new metaheuristic learning method that significantly improves the quality of solutions obtained.     

Multi-level,single-machine lot sizing and scheduling (with initial inventory)

This paper presents a mixed-integer program for the dynamic lot sizing and scheduling problem in a multi-level, single-machine environment. It turns out that in contrast to single-level problems the integration of initial inventory is a crucial aspect if generality should not be lost. It is shown how problem instances can efficiently be solved to suboptimality by using a so-called randomized regret based heuristic.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs

We consider the bicriteria scheduling problem of minimizing the number of tardy jobs and average flowtime on a single machine. This problem, which is known to be NP-hard, is important in practice, as the former criterion conveys the customer’s position, and the latter reflects the manufacturer’s perspective in the supply chain. We propose four new heuristics to solve this multiobjective scheduling problem. Two of these heuristics are constructive algorithms based on beam search methodology. The other two are metaheuristic approaches using a genetic algorithm and tabu-search. Our computational experiments indicate that the proposed beam search heuristics find efficient schedules optimally in most cases and perform better than the existing heuristics in the literature.