Hierarchical production and setup scheduling in stochasticmanufacturing systems

This paper is concerned with an asymptotic analysis of hierarchical production and setup scheduling in a stochastic manufacturing system consisting of a single failure-prone machine and facing constant demands for a number of products. At any given time the system can only produce one type of product, and the system requires a setup if production is to be switched from one type of product to another. A setup may involve setup time or setup cost or both. The objective of the problem is to minimize the total costs of setup, production, and surplus. The control variables are a sequence of setups and a production plan. An asymptotic analysis with respect to increasing rates of change in machine states gives rise to a deterministic limiting optimal control problem in which there is a control variable associated with each of the machine states and the production rate is obtained by weighting these controls with the stationary probabilities of the corresponding states. Asymptotic optimal controls for the original problem from optimal or near-optimal controls for the limiting problem are constructed     

制造系统的递阶滚动优化调度模型

研究的对象是只有一台不可靠（failure-prone)机器的非完全柔性制造系统，该系统能生产多种产品，但在同一时刻只能生产一种产品，并且当机器由生产一种产品向生产另一种产品切换时，需要考虑setup时间及其成本，待决策变量是setup序列及产品生产率，本文基于非完全柔性制造系统的特点，引入递阶层控的思想，采用新的递阶结构框架和阈值控制策略，对问题进行分解，建立了考虑setup时间及成本的递阶流率控制最优化调度模型，并给出了递阶的滚动优化算法，仿真结果表明，这种调度策略更易于工程实现。     

印染行业不可靠生产系统生产控制模型

基于印染行业自身特性,建立了适合于该行业特点的不可靠生产系统的生产控制模型。该模型不但考虑了生产设备时有故障和修复事件的发生,而且也把由于生产系统操作条件及生产原料属性的波动造成合格产品呈随机分布的情况纳入模型框架,其中当不同产品间生产切换时,所需切换时间及切换费用也被引入模型,并假设此时设备的故障过程为Markov过程。结合单设备单产品情况,给出了其最优生产控制策略。为实现印染行业生产的优化控制及建立完善的MES系统提供了理论支持。     

Scheduling of an unreliable manufacturing system with nonresumable setups

This paper considers the scheduling of a manufacturing system with nonresumable setup changes. The system considered involves an unreliable machine that can produce two part types. The switchover from one part type to the other incurs a given constant setup time. The setups are nonresumable, i.e. after a machine repair completion, a setup decision has to be made. The parts have specified constant processing time and constant demand rate. We give a continuous dynamic programming formulation of the problem, which is solved numerically. The optimal setup switching policies are shown to be hedging corridors. Two heuristics, for the determination of the hedging levels, are provided. We show, through simulation, that the two heuristics exhibit good performance.     

A heuristic approach for single-machine scheduling with due dates and class setups

The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete.     

Capacitated lot-sizing and scheduling with sequence-dependent,period-overlapping and non-triangular setups

In production planning, sequence dependent setup times and costs are often incurred for switchovers from one product to another. When setup times and costs do not respect the triangular inequality, a situation may occur where the optimal solution includes more than one batch of the same product in a single period—in other words, at least one sub tour exists in the production sequence of that period. By allowing setup crossovers, flexibility is increased and better solutions can be found. In tight capacity conditions, or whenever setup times are significant, setup crossovers are needed to assure feasibility. We present the first linear mixed-integer programming extension for the capacitated lot-sizing and scheduling problem incorporating all the necessary features of sequence sub tours and setup crossovers. This formulation is more efficient than other well known lot-sizing and scheduling models.     

Production/inventory systems with a stochastic production rate under a continuous review policy

A single production facility is dedicated to producing one product with completed units going directly into inventory. The unit production time is a random variable. The demand for the product is given by a Poisson process and is supplied directly from inventory when available, or is backordered until it is produced by the production facility. Relevant costs are a linear inventory holding cost, a linear backorder cost, and a fixed setup cost for initiating a production run. The objective is to find a control policy that minimizes the expected cost per time unit.The problem may be modeled as an M/G/1 queueing system, for which the optimal decision policy is a two-critical-number policy. Cost expressions are derived as functions of the policy parameters, and based on convexity properties of these cost expressions, an efficient search procedure is proposed for finding the optimal policy. Computational test results demonstrating the efficiency of the search procedure and the behavior of the optimal policy are presented.     

Optimal control structure of an unreliable manufacturing systemwith random demands

This paper considers an unreliable manufacturing system with random processing times and random product demands. The system can produce many part types and its total capacity is constrained by a fixed constant. The objective is to find an optimal service-rate allocation policy between different part types by minimizing the expected discounted inventory and backlog cost. Structural properties of the optimal control policy are investigated. It is shown that the optimal policy is of a switching structure. For producing a one part type case, the optimal control is a threshold policy. For producing a two part types case, the optimal control can be described by three monotone switching curves and its asymptote properties are derived. Numeric examples are given to illustrate the results     

Optimal layout and reconfiguration of a fixturing system constructed from passive Stewart platforms

The distinguishing property of Reconfigurable Manufacturing Systems (RMS) is that they can rapidly and efficiently adapt to new production requirements, both in terms of their capacity and functionalities. For this type of systems to achieve the desired efficiency, it should be possible to easily and quickly setup and reconfigure all of their components. This includes fixturing jigs that are used to hold workpieces firmly in place to enable a robot to carry out the desired production processes.In this paper, we formulate a constrained nonlinear optimization problem that must be solved to determine an optimal layout of reconfigurable fixtures for a given set of workpieces. The optimization problem takes into account the kinematic limitations of the fixtures, which are built in shape of Sterwart platforms, and the characteristics of the workpieces that need to be fastened into the fixturing system. Experimental results are presented that demonstrate that the automatically computed fixturing system layouts satisfy different constraints typically imposed in production environments.     

A novel 0-1 linear integer programming model for dynamic machine-tool selection and operation allocation in a flexible manufacturing system

This paper considers a problem of dynamic machine-tool selection and operation allocation with part and tool movement policies in a flexible manufacturing system (FMS) environment. For this purpose, a novel 0-1 linear integer programming model is presented in such a way that each part and each tool can move during the production phase. It is assumed that there are a given set of tools and machines that can produce different kinds of orders (or part types). The objective of this model is to determine a machine-tool combination for each operation of the part type by minimizing some production costs, such as machining costs, setup costs, material handling costs and tool movement costs. In addition, due to the NP-hard nature of the problem, a new heuristic method based on five simple procedures (FSP) is proposed for solving the given problem, whose performance is tested on a number of randomly generated problems. The related results are compared with results obtained by a branch-and-bound method. It has been found that the proposed heuristic method gives good results in terms of objective function values and CPU times.     

Planning production using mathematical programming: The case of a woodturning company

Herein we present a case of production planning in a woodturning company. The company wishes to plan the turning of various types of products of different radii in a set of parallel machines (lathes) and with the following principal conditions: for each type of product there is a minimum production lot size; some lathes cannot manufacture every type of product; the production capacity of a lathe depends on the lathe itself and the type of product to be manufactured; the products are classified into families according to radius; and there is an intra-family setup time (for manufacturing different products that have the same radius) and an inter-family setup time (for consecutively manufacturing products that have different radii), which is longer; part of the production can be subcontracted; each type of product can be manufactured on different lathes and/or subcontracted; and the operators can work overtime, during which additional time they can simultaneously operate multiple lathes. The goal is to meet the demand at minimum cost, which includes the cost of any overtime plus that of any subcontracting. The problem was modelled and solved by mixed-integer linear programming (MILP). The company considers the results to be satisfactory.     

Preemptive scheduling on two parallel machines with a single server

This paper addresses a preemptive scheduling problem on two parallel machines with a single server. Each job has to be loaded (setup) by the server before being processed on the machines. The preemption is allowed in this paper. The goal is to minimize the makespan. We first show that it is no of use to preempt the job during its setup time. Namely, every optimal preemptive schedule can be converted to another optimal schedule where all the setup times are non-preemptively performed on one machine. We then present an algorithm with a tight bound of 4/3 for the general case. Furthermore, we show that the algorithm can produce optimal schedules for two special cases: equal processing times and equal setup times, which are NP-hard in the non-preemptive version.     

Research on optimization of setup time for product in the multi-product production system

Consumers' consumption habits are more and more personalized and diversified, which makes the multi-product production system has been applied extensively in the factory worldwide. This brings a difficult problem to a large number of manufacturing enterprises: how to optimize the setup time of the product to achieve the purpose of improving the time efficiency. Based on this problem, this paper proposes the TCP technology for the optimization of setup time, that is, using the Times Series model, the Clustering Algorithm, and the Parallel Job technology in the Single Minute Exchange of Die (SMED), to form an application framework focusing on optimizing the product setup time. The validity of the technology is verified by a case study. This paper enriches the research field of setup time optimization, production planning, and the application of the Clustering Algorithm in the multi-product production system. It provides a new way for manufacturing enterprises to pursue an excellent efficiency of product setup time.     

The economic production lot size model extended to include more than one production rate

We study an extension of the economic production lot size model, where more than one production rate can be used during a cycle. Moreover, the production rates, as well as their corresponding runtimes are decision variables. We decompose the problem into two subproblems. First, we show that all production rates should be chosen in the interval between the demand rate and the production rate which minimizes unit production costs, and should be used in an increasing order. Then, given the production rates, we derive closed‐form expressions for all optimal runtimes as well as the minimum average cost. This analysis reveals that it is the size of the setup cost that determines the need for being able to use several production rates. We also show how to derive a near‐optimal solution of the general problem.     

Multi-criteria sequence-dependent job shop scheduling using genetic algorithms

Real world job shops have to contend with jobs due on different days, material ready times that vary, reentrant workflows and sequence-dependent setup times. The problem is even more complex because businesses often judge solution goodness according to multiple competing criteria. Producing an optimal solution would be time consuming to the point of rendering the result meaningless. Commonly used heuristics such as shortest processing time (SPT) and earliest due date (EDD) can be used to calculate a feasible schedule quickly, but usually do not produce schedules that are close to optimal in these job shop environments. We demonstrate that genetic algorithms (GA) can be used to produce solutions in times comparable to common heuristics but closer to optimal. Changing criteria or their relative weights does not affect the running time, nor does it require programming changes. Therefore, a GA can be easily applied and modified for a variety of production optimization criteria in a job shop environment that includes sequence-dependent setup times.     

Scheduling concurrent production over a finite planning horizon: polynomially solvable cases

The paper analyzes a manufacturing system made up of one workstation which is able to produce concurrently a number of product types with controllable production rates in response to time-dependent product demands. Given a finite planning horizon, the objective is to minimize production cost, which is incurred when the workstation is not idle and inventory and backlog costs, which are incurred when the meeting of demand results in inventory surpluses and shortages. With the aid of the maximum principle, optimal production regimes are derived and continuous-time scheduling is reduced to a combinatorial problem of sequencing and timing the regimes. The problem is proved to be polynomially solvable if demand does not exceed the capacity of the workstation or it is steadily pressing and the costs are “agreeable”.

Scope and purpose

Efficient utilization of modern flexible manufacturing systems is heavily dependent on proper scheduling of products throughout the available facilities. Scheduling of a workstation which produces concurrently a number of product types with controllable production rates in response to continuous, time-dependent demand is under consideration. Similar to the systems considered by many authors in recent years, a buffer with unlimited capacity is placed after the workstation for each product type. The objective is to minimize inventory storage, backlog and production costs over a finite planning horizon. Numerical approaches are commonly used to approximate the optimal solution for similar problems. The key contribution of this work is that the continuous-time scheduling problem is reduced to a combinatorial problem, exactly solvable in polynomial time if demand does not exceed the capacity of the workstation or the manufacturing system is organized such that the early production and storage of a product to reduce later backlogs are justified.     

A heuristic for determination of optimal capacity of central storage

A system of one machine used to produce m products in batches and a central storage used for storing raw materials and finished products is considered. The system maintains enough finished products to assure no stockout will happen. The machine has a finite production rate greater than or equal to the demand rate for each product, and thus operates with periodic start-ups and shut-downs. For special case when set-up for each product requires time and every product is produced in every cycle, the best policy given limited storage space is determined, and total production cost as a function of set-up costs, carrying cost, storage cost, and material handling cost is presented. A heuristic is developed that determines “optimal feasible cycle time” such that production scheduling remains feasible, the capacity of the central storage is not exceeded, and the overall costs are minimized.     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

Optimal MRP offsetting for assembly systems with stochastic lead times: POQ policy and service level constraint

This study deals with component supply planning in assembly systems, i.e. where several types of components are needed to produce one finished product. The actual component lead times have random deviations, so they can be considered as random variables. MRP approach with Periodic Order Quantity policy is considered. The aim is to find the optimal MRP offsetting. The proposed model and algorithms minimize the sum of the setup and average holding costs for the components, while satisfying a desired service level.