Decomposition based heuristic algorithm for lot-sizing and scheduling problem treating time horizon as a continuum

In this paper, we deal with a new lot-sizing and scheduling problem (LSSP) that minimizes the sum of production cost, setup cost, and inventory cost. Incorporating the constraints of setup carry-over and overlapping as well as demand splitting, we develop a mixed integer programming (MIP) formulation. In the formulation, problem size does not increase as we enhance the precision level of a time period; for example, by dividing a time period into a number of microtime periods. Accordingly, in the proposed model, we treat the time horizon as a continuum not as a collection of discrete time periods. Since the problem is theoretically intractable, we develop a simple but efficient heuristic algorithm by devising a decomposition scheme coupled with a local search procedure. Even if in theory the heuristic may not guarantee finding a feasible solution, computational results demonstrate that the proposed algorithm is a viable choice in practice for finding good quality feasible solutions within acceptable time limit.     

The multi-item capacitated lot-sizing problem with safety stocks and demand shortage costs

We address a multi-item capacitated lot-sizing problem with setup times, safety stock and demand shortages. Demand cannot be backlogged, but can be totally or partially lost. Safety stock is an objective to reach rather than an industrial constraint to respect. The problem is np-hard. We propose a Lagrangian relaxation of the resource capacity constraints. We develop a dynamic programming algorithm to solve the induced sub-problems. An upper bound is also proposed using a Lagrangian heuristic with several smoothing algorithms. Some experimental results showing the effectiveness of the approach are reported.     

An optimal production lot-sizing problem for an imperfect process with imperfect maintenance and inspection time length

This article develops an integrated model in considering the situations of an imperfect process with imperfect maintenance and inspection time for the joint determination of both economic production quantity (EPQ) and preventive maintenance (PM). This imperfect process has a general deterioration distribution with increasing hazard rate. Even with periodic PM, such a production system cannot be recovered as good as new. This means that the system condition depends on how long it runs. Also, the PM level can be distinct due to the maintenance cost. For convenience, it is assumed the age of system is reduced in proportional to the PM level. Further, during a production cycle, we need an inspection to see if the process is in control. This inspection might demand a considerable amount of time. In this article, we take PM level and inspection time into consideration to optimise EPQ with two types of out-of-control states. To see how the method works, we use a Weibull shock model to show the optimal solutions for the least costs.     

Stochastic model of production and inventory control using dynamic bayesian network

Bayesian Network is a stochastic model, which shows the qualitative dependence between two or more random variables by the graph structure, and indicates the quantitative relations between individual variables by the conditional probability. This paper deals with the production and inventory control using the dynamic Bayesian network. The probabilistic values of the amount of delivered goods and the production quantities are changed in the real environment, and then the total stock is also changed randomly. The probabilistic distribution of the total stock is calculated through the propagation of the probability on the Bayesian network. Moreover, an adjusting rule of the production quantities to maintain the probability of the lower bound and the upper bound of the total stock to certain values is shown. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Markov decision models for the optimal maintenance of a production unit with an upstream buffer

We consider a manufacturing system in which a buffer has been placed between the input generator and the production unit. The input generator supplies at a constant rate the buffer with the raw material, which is pulled by the production unit. The pull-rate is greater than the input rate when the buffer is not empty. The two rates become equal as soon as the buffer is evacuated. The production unit deteriorates stochastically over time and the problem of its optimal preventive maintenance is considered. Under a suitable cost structure it is proved that the optimal average-cost policy for fixed buffer size is of control-limit type, if the repair times are geometrically distributed. Efficient Markov decision process solution algorithms that operate on the class of control-limit policies are developed, when the repair times are geometrical or follow a continuous distribution. The optimality of a control-limit policy is also proved when the production unit after the end of a maintenance remains idle until the buffer is filled up. Furthermore, numerical results are given for the optimal policy if it is permissible to leave the production unit idle whenever it is in operative condition.     

A note on “fuzzy multi-objective production/distribution planning decisions with multi-product and multi-time period in a supply chain”

Liang (2008) [Liang, T. -F. (2008). A note on “fuzzy multi-objective production/distribution planning decisions with multi-product and multi-time period in a supply chain”. Computers & Industrial Engineering, 55, 676–694] proposed a production/distribution planning model and its solution approach in fuzzy environment. However, his mathematical model does not use backordering option. The main purpose of this paper is to demonstrate this handicap and propose a valid constraint.     

Analysis of multi-stage production/inventory system with an acceptable response time

This paper describes a method to decide the inventory levels of semifinished and finished products so as to realize the target service rate by shipping the finished products within a specified time which we call the acceptable response time. We analyze the substitution relation between the acceptable response time and the inventory levels of semifinished and finished products. As a result, inventory levels required according to the length of the acceptable response time under the condition of satisfying the target service rate are obtained. The validity of our method is also demonstrated through simulation experiments with the conditions given by the analysis.     

基于面向对象的几何定理自动证明系统设计与实现

针对几何定理自动证明的前推法实现方式,结合面向对象编程工具的特点,实现了一个原型系统。该系统结构简单、清晰,可扩展性强,并能产生可读证明过程。实例分析说明了该原型的有效性。     

Periodic review fuzzy inventory model with variable lead time and fuzzy demand

This paper investigates a periodic review fuzzy inventory model with lead time, reorder point, and cycle length as decision variables. The main goal of this study is to minimize the expected total annual cost by simultaneously optimizing cycle length, reorder point, and lead time for the whole system based on fuzzy demand. Two models are considered in this paper: one with normal demand distribution and another with a distribution‐free approach. The model assumes a logarithmic investment function for lost‐sale rate reduction. Furthermore, two separate efficient computational algorithms are explained to obtain the optimal solution. Some numerical examples are given to illustrate the model.     

Solving single-product economic lot-sizing problem with non-increasing setup cost,constant capacity and convex inventory cost in O(N log N) time

This paper considers an economic lot sizing model with constant capacity, non-increasing setup cost, and convex inventory cost function. Algorithms with computational time of O(N×TD_N)have been developed for solving the model, where N is the number of planning periods and TD_N is the total demand. This study partially characterizes the optimal planning structure of the model. A new efficient algorithm with computational time of O(N log N) has also been developed based on the partial optimal structure. Moreover, computational study demonstrates that the new algorithm is efficient.     

An alternative simple solution algorithm of an inventory model with fixed and variable lead time crash costs under unknown demand distribution

Inventory models with controllable lead time both for known and unknown demand distributions have been proposed in the literature. A model is useless unless it is formulated correctly and feasible. A simple solution procedure of a model also plays an important role in its application. This article highlights an erroneous formulation of an inventory model developed with fixed and variable lead time crash costs under unknown demand distribution, and also demonstrates its infeasibility. To attain feasibility we extend the model to include a constraint. Then, we present an alternative simple solution technique of the modified model and carry out a comparative study on a numerical example to show its potential significance.     

On a batch arrival Poisson queue with a random setup time and vacation period

The single server queue with vacation has been extended to include several types of extensions and generalisations, to which attention has been paid by several researchers (e.g. see Doshi, B. T., Single server queues with vacations — a servey. Queueing Systems, 1986, 1, 29–66; Takagi, H., Queueing Analysis: A Foundation of Performance evaluation, Vol. 1, Vacation and Priority systems, Part. 1. North Holland, Amsterdam, 1991; Medhi, J., Extensions and generalizations of the classical single server queueing system with Poisson input. J. Ass. Sci. Soc., 1994, 36, 35–41, etc.). The interest in such types of queues have been further enhanced in resent years because of their theoretical structures as well as their application in many real life situations such as computer, telecommunication, airline scheduling as well as production/inventory systems. This paper concerns the model building of such a production/inventory system, where machine undergoes extra operation (such as machine repair, preventive maintenance, gearing up machinery, etc.) before the processing of raw material is to be started. To be realistic, we also assume that raw materials arrive in batch. This production system can be formulated as an M^x/M/1 queues with a setup time. Further, from the utility point of view of idle time this model can also be formulated as a case of multiple vacation model, where vacation begins at the end of each busy period. Besides, the production/inventory systems, such a model is generally fitted to airline scheduling problems also. In this paper an attempt has been made to study the steady state behavior of such an M^x/M/1 queueing system with a view to provide some system performance measures, which lead to remarkable simplification when solving other similar types of queueing models.This paper deals with the steady state behaviour of a single server batch arrival Poisson queue with a random setup time and a vacation period. The service of the first customer in each busy period is preceded by a random setup period, on completion of which service starts. As soon as the system becomes empty the server goes on vacation for a random length of time. On return from vacation, if he finds customer(s) waiting, the server starts servicing the first customer in the queue. Otherwise it takes another vacation and so on. We study the steady state behaviour of the queue size distribution at random (stationary) point of time as well as at departure point of time and try to show that departure point queue size distribution can be decomposed into three independent random variables, one of which is the queue size of the standard M^x/M/1 queue. The interpretation of the other two random variables will also be provided. Further, we derive analytically explicit expressions for the system state (number of customers in the system) probabilities and provide their appropriate interpretations. Also, we derive some system performance measures. Finally, we develop a procedure to find mean waiting time of an arbitrary customer.