Using real time information for effective dynamic scheduling

In many production processes real time information may be obtained from process control computers and other monitoring systems, but most existing scheduling models are unable to use this information to effectively influence scheduling decisions in real time. In this paper we develop a general framework for using real time information to improve scheduling decisions, which allows us to trade off the quality of the revised schedule against the production disturbance which results from changing the planned schedule. We illustrate how our framework can be used to select a strategy for using real time information for a single machine scheduling model and discuss how it may be used to incorporate real time information into scheduling the complex production processes of steel continuous caster planning.     

Multi-level lotsizing and scheduling by batch sequencing

We consider a single-machine scheduling problem with a multi-level product structure. Setups are required if the machine changes production from one product type to another, and the scheduling decision must satisfy dynamic demand. We propose a lotsizing as well as a scheduling model, and we compare solution procedures for both models on a very restricted set of instances. As a result the multi-level structure complicates the inventory balance constraints in the lotsizing model. In the scheduling model, however, the multi-level structure translates into precedence constraints between jobs (leading to a smaller search space) which allows it to solve the scheduling model to optimality.     

Modelling and scheduling of an asynchronous cyclic production line with multiple parts

In this study, we model and analyse a production line with asynchronous part transfers, processing time variability, and cyclic scheduling in the same framework. We consider a production line with multiple parts and finite interstation buffers. The line produces a batch of n jobs repetitively using the same order of jobs in every batch. The processing time of a job on a station is a random variable and is assumed to have a phase-type distribution. Parts are transferred between the stations in an asynchronous manner. We first present a continuous time Markov chain model to analyse the performance of this system for a given sequence. A state-space representation of the model and the associated rate matrix are generated automatically. The steady state probabilities of the Markov chain are determined by using a recursive method that exploits the special structure of the rate matrix. The cycle time, the production rate, and the expected Work-In-Progress (WIP) inventory are used as the main performance measures. We then present an approximate procedure to determine the cyclic sequence that minimises the cycle time. We then investigate the effects of operating decisions, system structure, processing time variability, and their interaction in the same framework. Numerical results for the performance evaluation and scheduling of cyclic production lines are also presented.     

A stochastic linear programming approach to hierarchical production planning

This paper examines production planning decisions. The process is formulated as a hierarchical production planning (HPP) model under uncertain demand. A review of HPP articles indicates that while current models do consider uncertainty as a part of their solution methods, a deficiency persists since these models fail to incorporate the uncertain demand explicitly in the formulation of the problem. A stochastic linear programming model (SLP) is proposed to better reflect reality and to provide a superior solution. The model remains computationally tractable despite the precise incorporation of uncertainty and the imposition of penalties when constraints are violated. A problem is introduced which illustrates the superiority of the proposed model over those currently being applied.     

A hierarchical scheduling problem with a well-solvable second stage

In the hierarchical scheduling model to be considered, the decision at the aggregate level to acquire a number of identical machines has to be based on probabilistic information about the jobs that have to be scheduled on these machines at the detailed level. The objective is to minimize the sum of the acquisition costs and the expected average completion time of the jobs. In contrast to previous models of this type, the second part of this objective function corresponds to a well-solvable scheduling problem that can be solved to optimality by a simple priority rule. A heuristic method to solve the entire problem is described, for which strong asymptotic optimality results can be established.     

Integrated production planning and order acceptance under uncertainty: A robust optimization approach

The aim of this paper is to formulate a model that integrates production planning and order acceptance decisions while taking into account demand uncertainty and capturing the effects of congestion. Orders/customers are classified into classes based on their marginal revenue and their level of variability in order quantity (demand variance). The proposed integrated model provides the flexibility to decide on the fraction of demand to be satisfied from each customer class, giving the planner the choice of selecting among the highly profitable yet risky orders or less profitable but possibly more stable orders. Furthermore, when the production stage exceeds a critical utilization level, it suffers the consequences of congestion via elongated lead-times which results in backorders and erodes the firm’s revenue. Through order acceptance decisions, the planner can maintain a reasonable level of utilization and hence avoid increasing delays in production lead times. A robust optimization (RO) approach is adapted to model demand uncertainty and non-linear clearing functions characterize the relationship between throughput and workload to reflect the effects of congestion on production lead times. Illustrative simulation and numerical experiments show characteristics of the integrated model, the effects of congestion and variability, and the value of integrating production planning and order acceptance decisions.     

考虑碳排放的多机可持续调度问题

考虑多机器生产环境下,研究在加工空档期允许关闭机器的可持续调度问题。同时对工件的指派、工件的开始加工时刻和机器在空档期是否开关机进行决策,以最小化碳排放为目标建立数学规划模型。设计了禁忌搜索混合算法求解模型,首先通过一个企业案例验证了模型和算法的有效性,然后通过仿真算例分析了算法的效率。计算结果表明,可持续调度方式在机器调度层面为企业减少了大量的碳排放。     

Time and inventory dependent optimal maintenance policies for single machine workstations: An MDP approach

In this work the problem of obtaining an optimal maintenance policy for a single-machine, single-product workstation that deteriorates over time is addressed, using Markov Decision Process (MDP) models. Two models are proposed. The decision criteria for the first model is based on the cost of performing maintenance, the cost of repairing a failed machine and the cost of holding inventory while the machine is not available for production. For the second model the cost of holding inventory is replaced by the cost of not satisfying the demand. The processing time of jobs, inter-arrival times of jobs or units of demand, and the failure times are assumed to be random. The results show that in order to make better maintenance decisions the interaction between the inventory (whether in process or final), and the number of shifts that the machine has been working without restoration, has to be taken into account. If this interaction is considered, the long-run operational costs are reduced significantly. Moreover, structural properties of the optimal policies of the models are obtained after imposing conditions on the parameters of the models and on the distribution of the lifetime of a recently restored machine.     

Joint production and preventive maintenance scheduling for a single degraded machine by considering machine failures

Production scheduling and maintenance planning are two interdependent issues that most often have been investigated independently. Although both preventive maintenance (PM) and minimal repair affect availability and failure rate of a machine, only a few researchers have considered this interdependency in the literature. Furthermore, most of the existing joint production and preventive maintenance scheduling methods assume that machine is available during the planning horizon and consider only a possible level for PM. In this research, an integrated model is proposed that coordinates preventive maintenance planning with single-machine scheduling to minimize the weighted completion time of jobs and maintenance cost, simultaneously. This paper not only considers multiple PM levels with different costs, times and reductions in the hazard rate of the machine, but also assumes that a machine failure may occur at any time. To illustrate the effectiveness of the suggested method, it is compared to two situations of no PM and a single PM level. Eventually, to tackle the suggested problem, multi-objective particle swarm optimization and non-dominated sorting genetic algorithm (NSGA-II) are employed and their parameters are tuned Furthermore, their performances are compared in terms of three metrics criteria.     

Aggregation and the design of models for medium-term planning of production

A major issue in the design of an aggregate multi-period model for medium-term planning of production is the determination of the aggregation level of the variables. In the process of model design, one has to examine if and how the outcomes of the model are effected by applying different modes and levels of aggregation. This is especially important with regard to those outcomes which will be used for medium-term decisions and for laying out short-term and detailed plans. Also dependent on the aggregation level is the operational convenience of the model for decision support. In this paper it will be shown that simulation experiments with a preliminary model for medium-term planning can yield valuable information to aid this design problem.     

Design of mathematical models for the integration of purchase and production lot-sizing and scheduling problems under demand uncertainty

This study addresses the multi-level lot-sizing and scheduling problem with complex setups and considers supplier selection with quantity discounts and multiple modes of transportation. The present research proposes a mixed-integer linear programming (MILP) model in which the purchase lot-sizing from multiple suppliers, production lot-sizing with multiple machines and scheduling of various products of different families are accomplished at the same time. However, these decisions are not integrated in traditional environments and are taken separately. In this study, two different types of lot-sizing models called aggregated and disaggregated are developed for the problem to evaluate and compare the computational efficiency of them under deterministic and stochastic demands and provide some managerial insights. To deal with the stochastic demands, Chance-Constrained Programming (CCP) approach is applied. Based on the results of this study, the average profit of the separated (purchase from production) lot-sizing model under demand choice flexibility and stochastic demand is 24% and 22% less than the integrated model, respectively. Moreover, the results also confirm the effect of discount structure on the amount of purchases, productions, revenues and costs.     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

Using profit maximizing scheduling models to structure operational trade-offs and manufacturing strategy issues

Manufacturing plays an increasingly important role in determining the competitiveness of the firm. However, corporate strategy is often formulated with little regard for how these decisions affect operations within the manufacturing system. Detailed models provide a necessary link between manufacturing performance and the functional policies followed by the firm, so that the strengths of the manufacturing system can be consistently reflected in strategic decisions.This paper presents a scheduling model that relates the strategic decisions that determine the type of work that must ultimately be processed by the manufacturing system with the detailed decisions that determine how this work should be scheduled. The model accounts for varying processing time, delay penalty, and revenue characteristics among the jobs available for processing by a single facility, with jobs partitioned in multiple classes such that a setup is incurred each time two jobs of different classes are processed in succession. Given limited processing capacity, the objective is to simultaneously determine the subset of jobs to accept for processing and the associated order in which accepted jobs should be sequenced to maximize the total profit realized by the facility. Problem formulations and dynamic programming algorithms are presented for both the special case in which all available work is from a single job class, and the more general case involving multiple job classes. The insight derived from these models concerning the operational implications of strategic decisions is illustrated through a series of example problems, first focusing on the coordination of marketing and manufacturing policy, and finally by considering important issues related to manufacturing focus.     

Planning horizons for multi-item hierarchical production scheduling problems: A heuristic search procedure

A proper planning horizon is important to the effectiveness of planning results. However, there is no planning horizon study dealing with multi-item, multi-level production planning problems which are often encountered in reality. In this study, we develop a direct search procedure for finding planning horizons for a multi-item hierarchical production planning process which consists of an aggregate planning problem and a master production scheduling problem. Experimental results show that the search heuristic is quite efficient in finding planning horizons for both aggregate planning problem and the master scheduling problem. The results also show that the master schedule planning horizons need not be longer than the aggregate planning horizons.     

Batch machine production with perishability time windows and limited batch size

This article provides a theoretical analysis of the problem of scheduling jobs in batches by family on a batch-processing machine, in the presence of perishability time windows of equal length. The problem arises in the context of production planning in a microbiological laboratory, and has application in wafer-fab production and for wireless broadcasting. The combined features of multiple families and time windows are new to the literature. The study is restricted to unit job processing times. We prove that the problem is NP-hard, thus solving an open problem by Uzsoy [24]. A Dynamic Programme is developed, with running time polynomial in the input variables of maximum batch size, the number of families and the length of the demand time horizon. In addition, we show that an heuristic approach to minimising the perishability time window can provide a 2-approximation to the optimum.     

A bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

Using shared sell-through data to forecast wholesaler demand in multi-echelon supply chains

Operational forecasting in supply chain management supports a variety of short-term planning decisions, such as production scheduling and inventory management. In this respect, improving short-term forecast accuracy is a way to build a more agile supply chain for manufacturing companies. Demand forecasting often relies on well-established univariate forecasting methods to extrapolate historical demand. Collaboration across the supply chain, including information sharing, is suggested in the literature to improve upon the forecast accuracy of such traditional methods. In this paper, we review empirical studies considering the use of downstream information in demand forecasting and investigate different modeling approaches and forecasting methods to incorporate such data. Where empirical findings on information sharing mainly focus on point-of-sale data in two-level supply chains, this research empirically investigates the added value of using sell-through data originating from intermediaries, next to historical demand figures, in a multi-echelon supply chain. In a case study concerning a US drug manufacturer, we evaluate different methods to incorporate this data and consider both time series methods and machine learning techniques to produce multi-step ahead weekly forecasts. The results show that the manufacturer can effectively improve its short-term forecast accuracy by integrating sell-through data into the forecasting process and provide useful insights as to the different modeling approaches used. The conclusion holds for all forecast horizons considered, though it is most pronounced for one-step ahead forecasts. Therefore, our research provides a clear incentive for manufacturers to assess the forecast accuracy that can be achieved by using sell-through data.     

Batch scheduling and common due-date assignment on a single machine

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.     

Hierarchical design of an integrated production and 2-echelon distribution system

This study uses the method of Lagrangean relaxation in the hierarchical design of an integrated model of production–distribution functions in a 2-echelon system. A mixed integer mathematical model is developed with a centralized planning perspective to address production and distribution decisions simultaneously. In order to solve the resulting large-scale problem, the Lagrangean relaxation is used to decouple the imbedded distribution and production subproblems, and subgradient optimization is implemented to coordinate the information flow between these in a hierarchical manner. This corresponds to a decentralized organizational design where a central agent coordinates the information exchange between the distribution and production organizational units. A forward heuristic designed to solve the distribution subproblem is shown to provide good solutions. Hierarchical interdependency is incorporated into the Lagrangean heuristic such that distribution decisions are placed in the top level to restrict the solution of the production subproblem in the lower level.     

Competitive production scheduling: A two-firm,noncooperative finite dynamic game

In this paper, we study the production scheduling problem in a competitive environment. Two firms produce the same product and compete in a market. The demand is random and so is the production capacity of each firm, due to random breakdowns. We consider a finite planning horizon. The scheduling problem is formulated as a finite dynamic game. Algorithms are developed to determine the security, hazard, and Nash policies. Numerical examples are discussed. A single-firm optimization model is also analyzed and it is observed that the production control policy from the single-firm optimization model may not perform well in a competitive environment.