Optimal production control of a dynamic two-product manufacturing system with setup costs and setup times

This paper deals with the optimal control of a one-machine two-product manufacturing system with setup changes, operating in a continuous time dynamic environment. The system is deterministic. When production is switched from one product to the other, a known constant setup time and a setup cost are incurred. Each product has specified constant processing time and constant demand rate, as well as an infinite supply of raw material. The problem is formulated as a feedback control problem. The objective is to minimize the total backlog, inventory and setup costs incurred over a finite horizon. The optimal solution provides the optimal production rate and setup switching epochs as a function of the state of the system (backlog and inventory levels). For the steady state, the optimal cyclic schedule is determined. To solve the transient case, the system's state space is partitioned into mutually exclusive regions such that with each region, the optimal control policy is determined analytically.     

具有定价和开机成本的生产-库存系统的最优(s,d,S)策略

考虑一个具有有限容量和开机成本的连续盘点生产-库存系统, 其控制策略为(s,d,S)策略. 未被满足的需求都会丢失. 当机器处于关闭状态时,库存产品可以两个不同的价格进行销售. 当机器处于开机状态时,库存只能以较高的价格进行销售. 研究了如何发现该系统下的最优(s,d,S)策略,并开发了用于计算最优控制参数的有效算法.     

Infinitesimal perturbation analysis for second derivative estimation and design of manufacturing flow controllers

A simulation-based numerical technique for the design of near-optimal manufacturing flow controllers for unreliable flexible manufacturing systems uses quadratic approximations of the value functions that characterize the optimal policy and employs stochastic optimization to design the key coefficients of the quadratic approximations. First and second derivative estimates that drive the optimization algorithm are obtained from a single sample path of the system via infinitesimal perturbation analysis (IPA). Extensive computational experience is reported for one, two, and three-part-type production systems. The relative performance of first-order and second-order stochastic optimization algorithms is investigated. The computational efficiency of these algorithms is finally compared to conventional controller design algorithms based on state-space discretization and successive approximation.This research was supported by the National Science Foundation, Grant No. DDM-89-14277 and DDM-9215368.     

A branch and bound method for the job-shop problem with sequence-dependent setup times

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.     

Cost-effective production policy for a stochastic unreliable manufacturing system

^** Email: dohi{at}rel.hiroshima-u.ac.jp The paper deals with an economic manufacturing quantity (EMQ)problem for an unreliable manufacturing system in both continuous-and discrete-time settings. The time to machine failure andcorrective and preventive repair times of the production facilityare assumed to follow arbitrary probability distributions. Thetraditional method of determining the EMQ policy for a failure-pronemanufacturing system is based on the minimization of the long-runaverage cost in the steady state. In this paper, an alternativecriterion of optimality called cost effectiveness is introduced.The criteria for the existence and uniqueness of the optimalproduction time maximizing the cost effectiveness are derivedanalytically under general failure and specific repair (correctiveand preventive) time distributions. The optimal cost-effectiveand average cost production policies are numerically calculatedand compared in terms of their performances.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

A numerical method to approximate optimal production and maintenance plan in a flexible manufacturing system

The simultaneous planning of the production and the maintenance in a flexible manufacturing system is considered in this paper. The manufacturing system is composed of one machine that produces a single product. There is a preventive maintenance plan to reduce the failure rate of the machine. This paper is different from the previous researches in this area in two separate ways. First, the failure rate of the machine is supposed to be a function of its age. Second, we assume that the demand of the manufacturing product is time dependent and its rate depends on the level of advertisement on that product. The objective is to maximize the expected discounted total profit of the firm over an infinite time horizon. In the process of finding a solution to the problem, we first characterize an optimal control by introducing a set of Hamilton–Jacobi–Bellman partial differential equations. Then we realize that under practical assumptions, this set of equations can not be solved analytically. Thus to find a suboptimal control, we approximate the original stochastic optimal control model by a discrete-time deterministic optimal control problem. Then proposing a numerical method to solve the steady state Riccati equation, we approximate a suboptimal solution to the problem.     

A note on conservation laws for a multiclass service queueing system with setup times

This paper derives a conservation law for mean waiting times in a single-server multi-class service queueing system (M ^X/G/1 type queue) with setup times which may be dependent on multiple customer classes and its arrival batch size by using the work decomposition property in the queueing system with vacations.     

Hierarchical production control of a flexible manufacturing system

A hierarchical production control framework for a flexible manufacturing system is proposed. The machines in the system are subject to failures in a wide spectrum band. At first, failures are clustered near some discrete points on the failure spectrum in order to define the hierarchical model. Each level in the hierarchy corresponds to a discrete point on the failure spectrum. At each level, faster varying failures are modelled by their mean behaviour, and more slowly varying failures are treated as static. Then, a hierarchical controller of multiple time scale type is proposed. System control at each level is based on the work of Kimemia and Gershwin. Simulation results conclude the paper.     

Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates

This paper studies the scheduling problem in hybrid flow shop (HFS) environment. The sequence dependent family setup time (SDFST) is concerned with minimization of makespan and total tardiness. Production environments in real world include innumerable cases of uncertainty and stochasticity of events and a suitable scheduling model should consider them. Hence, in this paper, due date is assumed to be uncertain and its data follow a normal distribution. Since the proposed problem is NP-hard, two metaheuristic algorithms are presented based on genetic algorithm, namely: Non-dominated Sorting Genetic Algorithm (NSGAII) and Multi Objective Genetic Algorithm (MOGA). The quantitative and qualitative results of these two algorithms have been compared in different dimensions with multi phase genetic algorithm (MPGA) used in literature review. Experimental results indicate that the NSGAII performs very well when compared against MOGA and MPGA in a considerably shorter time.     

Production and replacement policies for a deteriorating manufacturing system under random demand and quality

This work investigates the production planning of an unreliable deteriorating manufacturing system under uncertainties. The effect of the deterioration phenomenon on the machine is mainly observed in its availability and the quality of the parts produced, with the rates of failure and defectives increasing with the age of the machine. The option to replace the machine should be considered to mitigate the effect of deterioration in order to ensure long-term satisfaction of demand. The objective of this paper is to find the production rate and the replacement policy that minimize the total discounted cost, which includes inventory, backlog, production, repair and replacement costs, over an infinite planning horizon. We formulate the stochastic control problem in the framework of a semi-Markov decision process to consider the machine's history. The integration of random demand and quality behaviour led us to propose a new modeling approach by developing optimality conditions in terms of a second-order approximation of Hamilton–Jacobi–Bellman (HJB) equations. Numerical methods are used to obtain the optimal control policies. Finally, a numerical example and a sensitivity analysis are presented in order to illustrate and confirm the structure of the optimal solution obtained.     

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.     

A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness

This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods.     

On a BMAP/G/1 G-queue with setup times and multiple vacations

In this paper, we consider a BMAP/G/1 G-queue with setup times and multiple vacations. Arrivals of positive customers and negative customers follow a batch Markovian arrival process (BMAP) and Markovian arrival process (MAP) respectively. The arrival of a negative customer removes all the customers in the system when the server is working. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. By using the supplementary variables method and the censoring technique, we obtain the queue length distributions. We also obtain the mean of the busy period based on the renewal theory.     

Turnpike properties for a class of piecewise deterministic systems arising in manufacturing flow control

This paper deals with a general class of piecewise deterministic control systems that encompasses FMS flow control models. One uses the Markov renewal decision process formalism to characterize optimal policies via a discrete event dynamic programming approach. A family of control problems with a random stopping time is associated with these optimality conditions. These problems can be reformulated as infinite horizon deterministic control problems. It is then shown how the so-calledturnpike property should hold for these deterministic control problems under classical convexity assumptions. These turnpikes have the same generic properties as the attractors obtained via a problem specific approach in FMS flow control models and production planning and are calledhedging points in this literature.This research has been supported by NSERC-Canada, Grants No. A4952 by FCAR-Québec, Grant No. 88EQ3528, Actions Structurantes, MESS-Québec, Grant No. 6.1/7.4(28), and FNRS-Switzerland.     

An efficient method to determine the optimal configuration of a flexible manufacturing system

A frequently encountered design issue for a flexible manufacturing system (FMS) is to find the lowest cost configuration, i.e. the number of resources of each type (machines, pallets, ...), which achieves a given production rate. In this paper, an efficient method to determine this optimal configuration is presented. The FMS is modelled as a closed queueing network. The proposed procedure first derives a heuristic solution and then the optimal solution. The computational complexity for finding the optimal solution is very reasonable even for large systems, except in some extreme cases. Moreover, the heuristic solution can always be determined and is very close (and often equal) to the optimal solution. A comparison with the previous method of Vinod and Solberg shows that our method performs very well.     

An analysis of setup cost reduction in a two stage system with power investment function

Recently, a framework for analyzing investment decisions as they relate to setup cost reduction in two stage production processes has appeared in the literature. Closed form results were developed for the case of logarithmic investment function. This paper extends the results to the case of power investment function. We present an algorithm for calculating the optimal values of the decision variables. A numerical example is utilized to reveal some interesting aspects of this system.     

Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period

In this article, we consider the single machine scheduling problem with one planned setup period, with the aim of minimizing the weighted sum of the completion times. We study the WSPT and MWSPT heuristics and we show that the worst-case performance ratio is 3 for the two heuristics in some cases and it is unbounded otherwise. We also show that these worst-case performance ratios are tight.     

Monotonicity of optimal flow control for failure-prone production systems

In this paper, we consider the problem of the optimal flow control for a production system with one machine which is subject to failures and produces one part type. In most previous work, it has been assumed that the machine has exponential up and down times, i.e., its state process is a Markov process. The system considered in our study has general machine up and down times. Our main result is establishing monotone properties for the optimal control policy.This work was partially supported by the National Science Foundation under Grants DDM-9215368 and EDI-9212122. The authors thank two anonymous reviewers for helpful comments and suggestions.     

On the optimal control of a single-server queueing system: Comment

In a recent paper by Scott and Jefferson, the optimal control of the service rate for a single-server queue with limited waiting space is treated by the maximum principle. We show that their control policies are necessarily suboptimal. Characterizations for optimal control are derived and used to obtain corresponding optimal trajectories in both nonsingular and singular regions.