Parallel-machine,multiple-product-type,continuous-time scheduling: decomposable cases

This paper considers a manufacturing system where multiple-product-types are produced on a set of parallel machines. The production quantity for each product-type in a planning horizon is predetermined. However, the planning horizon is not fixed, and a cost must be paid for each unit of time in the horizon. Inventory holding costs are incurred due to storing products in the buffer placed after each machine. In addition, a production cost is incurred if a machine is not idle. Our objective is to schedule the production so that inventory, production, and planning horizon costs are minimized. With the aid of the maximum principle, this continuous-time scheduling problem is studied, and the conditions such that the problem can be decomposed into a set of well-structured, discrete-time sub-problems are derived. Consequently, several solvable cases are identified, and their corresponding polynomial-time algorithms are suggested.     

A methodology for determining auxiliary and value-added electricity in manufacturing machines

A methodology was developed that accurately and flexibly determines the auxiliary (AU) and value-added electricity in manufacturing operations. A tool was developed for production engineers which allows for the verification of machine efficiency in relation to their energy consumption. Historical production and electricity consumption data were collected for a period of three months from four different machines in a value stream at a manufacturing facility. The data were examined using a methodology based on statistical analysis of the historical data collected and were verified using heuristic machines profiles. Results showed AU electricity consumption varied between 10 and 26% per machine. When weekend data (non-productive periods) were excluded from calculations, AU electricity consumption reduced. Past work focuses on optimising single machine, and the quantification of wasted electricity is not always clear. This research work can be applied to one or more machines, and to single or multiple products passing through the same machine. It places particular attention to AU electricity since potential energy and cost reduction of up to 20% could be achieved. Hence, this work can aid in developing key performance indicators to measure energy usage in manufacturing operations, particularly focused towards reducing AU electricity consumption.     

Selective disassembly sequencing with random operation times in parallel disassembly environment

Selective disassembly sequencing is the problem of determining the sequence of disassembly operations to extract one or more target components of a product. This study considers the problem with random operation times in the parallel disassembly environment in which one or more components can be removed at the same time by a single disassembly operation. After representing all possible disassembly sequences using the extended process graph, a stochastic integer programming model is developed for the objective of minimising the sum of disassembly and penalty costs, where the disassembly costs consist of sequence-dependent set-up and operation costs and the penalty cost is the expectation of the costs incurred when the total disassembly time exceeds a threshold value. A sample average approximation-based solution algorithm is proposed that incorporates an optimal algorithm to solve the sample average approximating problem under a given set of scenarios for disassembly operation times. The algorithm is illustrated with a hand-light case and a large-sized random instance, and the results are reported.     

The replacement of machines in a serially dependent multi-machine production system

In this paper a heuristic procedure is developed for solving the problem of planning machine replacements for a serially dependent production system. Given a finite planning horizon, the decision-maker wishes to decide (1) which periods, if any, that the entire production system must be shut down in order to make replacements, and (2) what specific machine or machines in the system should be scheduled for replacement during each of these downtime periods. The problem involves a balancing of costs. If the production system is brought down to make one or more replacements a fixed downtime cost is incurred; this cost is independent of the machines replaced during the downtime. In addition, other fixed coats are incurred for each of the machines replaced. Our motivation for scheduling these replacements is to realize lower variable costs for operating the machines. The variable operating costs are assumed to increase as the age or vintage of the machines increases. An optimal replacement policy is one in which the total of the present-value fixed and operating costs are minimized for the entire planning horizon. The paper also presents computational results using the heuristic to solve a large number of randomly generated test problems of varying numbers of machines and periods. These heuristic solutions are compared to known optimal solutions for a number of the problems. One of the important advantages of the heuristic procedure is that it is capable of producing several solutions to a given problem, all rank ordered by increasing cost. Thus, the decision-maker is afforded alternative choices from which he or she may select a replacement policy.     

Optimal machining conditions and buffer space size for the two-stage case

This paper presents a model for calculating optimal cutting speeds and tool replacement policies for both operations of a two-stage machining problem when the unit cost is minimized or the profit rate is maximized. The tool life is assumed to be a stochastic variable and penalty costs are imposed for tool failures during production. The optimal size of buffer space between the two machines is also calculated analytically. It is shown that the unit cost increases as the tool variability and/or the penalty cost increase. The cutting speeds and tool replacement policies on both operations depend strongly on the tool variability and the penalty cost. The cutting speeds differ from those determined independently for each operation. Finally, the optimal buffer space size is the one necessary to keep the critical machine running when there is a tool change on the non-critical machine, and its optimal size can be calculated analytically.     

Infinite horizon production planning with periodic demand: solvable cases and a general numerical approach

In this paper, we consider a single part-type pull manufacturing system, which controls its production rates in response to periodic demand. When tracking the demand results in a product surplus, an inventory storage cost is incurred. Likewise, if an overall shortage occurs then a backlog cost is paid. In addition, production costs accrue when the system is not idle. Given an infinite planning horizon, the objective is to determine the cyclic production rates in order to minimize the total cost. With the aid of the maximum principle, extremal behavior of the system is studied and the continuous-time production planning problem is reduced to a discrete problem with a limited number of switching points at which time the production rates change. Using this result, an efficient numerical algorithm is proposed, which will yield an approximation to the optimal solution within any desired level of accuracy. In addition, we determine the analytical solution to the problem for three special cases: (i) the system capacity is not limited and the inventory storage cost factor is equal to the backlog cost factor; (ii) the production cost is negligible; and (iii) the surplus and shortages costs are negligible.     

准时化(JIT)思想下有关交货期窗口的单机调度问题

研究了有关交货期窗口的单机调度问题。在过去的１０年中,准时化的概念对中国工业的影响很大。早于或晚于交货期窗口的任务都不受欢迎,且将导致提前或拖期惩罚。如果任务的完工时间偏离了交货期窗口,就要受到固定的惩罚,惩罚量与提前或拖期完工无关。目标是极小化所有惩罚的和。设如果任务在交货期准时完工,则不受惩罚;目标就是寻找一个最优调度极小化提前和拖期任务的总数。给出了确定最优调度的多项式时间算法,最后的例子说     

Storage Decisions in Information Systems

The problem is to dynamically store different data records in different storage devices in each period so as to minimize the total expected discounted cost over a planning horizon. Each device has a fixed total capacity, each record has a given storage space requirement, while the number of requests for each record per period is changing stochastically through time. Given an allocation, the total cost per period consists of the storage cost (depending on the storage requirements and device), the access cost including update and retrieval costs (depending on the number of requests) and the transfer cost (depending upon the change of allocation from the previous period). A dynamic programming model is presented to yield optimal strategies. The special case of independent identically distributed demands is completely solved, using a generalized transportation algorithm while a heuristic procedure is indicated for the general problem using parametric analysis.     

Scheduling of the optimal tool replacement times in a flexible manufacturing system

In Flexible Manufacturing Systems (FMSs). a cutting tool is frequently used for different operations and on different part types to minimize tool change-overs and the number of tools required, and to increase part-routing flexibility. In such situations, the tools become shared resources and work in job-dependent, changeable and nonhomogeneous conditions. It is well known that the tool failure rate depends on both age and machining conditions and that tool reliability is a function of the duration, machining conditions, and the sequence of the operations in FMS. The objective of this paper is to obtain a schedule of the optimal preventive replacement times for the cutting tools over a finite time horizon in a flexible manufacturing system. We assume that the tool will be replaced either upon failure during an operation or preventively after the completion of each operation, incurring different replacement costs. A standard stochastic dynamic programming approach is taken to obtain the optimal tool replacement times. The optimal schedule is obtained by minimizing the total expected cost over a finite time horizon for a given sequence of operations. A computational algorithm is developed and a numerical example is given to demonstrate the procedure.     

Hierarchical production control for a flow shop with dynamic setup changes and random machine breakdowns

In this paper, we study a manufacturing system consisting of two machines separated by two intermediate buffers, and capable of producing two different products. Each product requires a constant processing time on each of the machines. Each machine requires a constant non-negligible setup change time from one product to the other. The demand rate for each product is considered to be piecewise constant. Each machine undergoes failure and repair. The time-to-failure and time-to-repair are exponentially distributed random variables. The setup change and processing operations are resumable. We model our system as a continuous time, continuous flow process. An optimal control problem is formulated for the system to minimize the total expected discounted cost over an infinite horizon. To determine the optimal control policy structure, a discrete version of the problem is solved numerically using a dynamic programming formulation with a piecewise linear penalty function. A real-time control algorithm is then developed with the objective of maintaining low work-in-process inventory and keeping the production close to the demand. The algorithm uses a hierarchical control structure to generate the loading times for each product on each machine in real time and to respond to random disruptions in the system. The system is simulated using this algorithm to study its performance. The performance of the algorithm is also compared to alternative policies.     

Lot-sizing in a multi-stage flow line production system with energy consideration

In this paper, a single-item capacitated lot-sizing problem in a flow-shop system with energy consideration is studied. The planning horizon is defined by a set of periods where each one is characterised by a length, an allowed maximal power, an electricity price, a power price and a demand. The objective is to determine the quantities to be produced by each machine at each period while minimising the production cost in terms of electrical, inventory, set-up and power required costs. For medium- and large-scale problems, lot-sizing problems are hard to solve. Therefore, in this study, two heuristics are developed to solve this problem in a reasonable time. To evaluate the performances of these heuristics, computational experiments are presented and numerical results are discussed and analysed.     

Optimal and heuristic algorithms for the multi-location dynamic transshipment problem with fixed transshipment costs

We consider centrally controlled multi-location systems, which coordinate their replenishment strategies through the use of transshipments. In a dynamic deterministic demand environment the problem is characterized by several locations, each of which has known demand for a single product for each period in a given finite horizon. We consider replenishment, transshipment and inventory holding costs at each location, where the first two have location-dependent fixed, as well as linear components, and the third is linear and identical to all locations. We prove that the resulting dynamic transshipment problem is NP-hard, identify a special structure which is satisfied by an optimal solution and develop, based on this structure, an exponential time algorithm to solve the problem optimally. In addition, we develop a heuristic algorithm, based on partitioning the time horizon, which is capable of solving larger instances than the optimal solution. Our computational tests demonstrate that the heuristic performs extremely well.     

Single operation earliness–tardiness scheduling with machine activation costs

We consider a static, single operation, non-pre-emptive, deterministic scheduling problem in which a set of n jobs is to be processed on k identical machines. Jobs assigned to each machine have a common due date. The number of machines (k) is unknown. Activating a machine will require additional costs to be incurred. The objective is to find an optimal sequence, the optimal number of machines (k), and the respective due dates to minimize the weighted sum of earliness, tardiness, and machine activation costs. We propose a polynomial time algorithm to solve the problem.     

An economic model for raw material selection

An economic model for raw material selection is presented and a case analysis is given. The model considers two decision factors: initial raw material cost and additional manufacturing costs incurred due to inappropriateness of raw material quality. This additional manufacturing cost may include items such as: extra operator cost, extra machine cost and extra quality cost.     

The economic lot and delivery scheduling problem: the common cycle case

We analyze the interface between a supplier and an assembly facility, where direct shipments are made from one to the other. The final manufacturing step at the supplier involves multiple components produced on a single machine or production line. The assembly facility uses these components at a constant rate. The supplier incurs a sequence-independent setup cost and/or setup time each time the production line is changed over from one component to another. On the other hand, setup costs and times for the assembly facility are negligible. We consider two types of delivery cost: a fixed charge for each delivery, and a fixed-charge-per-truck cost.

We develop a heuristic procedure to find a 'just-in-time' schedule in which one production run of each product and a subsequent delivery of these products to the assembly facility occur in each cycle. The objective is to find the cycle duration that minimizes the average cost per unit time of transportation, inventory at both the supplier and the assembly facility, and setup costs at the supplier. We also develop an error bound for this procedure, and use some of the insights gained from the analysis to explain how delivery schedules can influence the attractiveness of reductions in production setup costs.     

Real-time disruption management in a two-stage production and inventory system

This paper presents a general disruption management approach for a two-stage production and inventory control system. A penalty cost for deviations of the new plan from the original plan is incorporated and the concept of a disruption recovery time window is introduced. We define two classes of problems: one with fixed setup epochs and another with flexible setup epochs. With linear or quadratic penalty functions for production/ordering quantity change and fixed setup epochs, the best recovery plan is obtained by solving a quadratic mathematical programming problem. With convex penalty functions for quantity changes and flexible setup epochs, it is shown that the second stage orders have identical order quantities within each production cycle. Therefore, in a lot-for-lot system, the ordering and production quantities for both stages are the same. As a special case, we consider disruption recovery problems with short time windows spanning one or two production cycles. We also discuss solution procedures for both major and minor disruption problems and give an extension for the case of multiple retailers. Throughout the paper managerial insights are presented that indicate how a company should respond to various types of disruptions during its operations.     

Processing and manufacturing of next generation lithium-based all solid-state batteries

All solid-state batteries are safe and potentially energy dense alternatives to conventional lithium ion batteries. However, current solid-state batteries are projected to costs well over $100/kWh. The high cost of solid-state batteries is attributed to both materials processing costs and low throughput manufacturing. Currently there are a range of solid electrolytes being examined and each material requires vastly different working environments and processing conditions. The processing environment (pressure and temperature) and cell operating conditions (pressure and temperature) influence costs. The need for high pressure during manufacturing and/or cell operation will ultimately increase plant footprint, costs, and machine operating times. Long term, for solid state batteries to become economical, conventional manufacturing approaches need to be adapted. In this perspective we discuss how material selection, processing approach, and system architecture will influence lithium-based solid state battery manufacturing.     

A combinatorial approach to a class of parallel-machine,continuous-time scheduling problems

The paper analyzes a manufacturing system with N non-identical, parallel machines continuously producing one product type in response to its demand. Inventory and backlog costs are incurred when tracking the demand results in inventory surpluses and shortages respectively. In addition, the production cost of a machine is incurred when the machine is not idle. The objective is to determine machine production rates so that the inventory, backlog, and production costs are minimized. For problems with demand defined as an arbitrary function of time, numerical methods are suggested to approximate an optimal solution. The complexity of the approximation methods is polynomial, while finding an exact optimal solution requires exponential time. In a case when production is to cope with a special form of a single-mode, K-level piece-wise constant demand, we prove, with the aid of the maximum principle, that the exact optimal solution can be found as a combination of analytical and combinatorial tools in O(KN ²( max {K,2N})²) time.     

A CAPACITY PLANNING MODEL FOR A MULTI-PRODUCT FACILITY

A deterministic capacity planning model for a multi-product facility is analyzed to determine (he sizes to be expanded (or disposed of) in each period so as to supply the known demand for N products on time and to minimize the total cost incurred over a finite planning horizon of T periods. The model assumes that each capacity unit of the facility simultaneously serves a prespecified number of demand units of each product, that costs considered include capacity expansion costs, capacity disposal costs, and excess (idle) capacity holding costs, and all the associated cost functions are nondecreasing and concave, and that backlogging is not allowed. The structure of an optimal solution is characterized and then used in developing an efficient dynamic programming algorithm that finds optimal capacity planning policies. The required computational effort is a polynomial function of N and T.     

A method for comparing flexibility performance for the lifecycle of manufacturing systems under capacity planning constraints

The objective of this work is to describe a method for comparing the flexibility performance of manufacturing systems, in an uncertain environment, under lifecycle considerations and capacity planning constraints. The manufacturing systems costs are estimated over a time horizon and for a large variety of possible market scenarios. In order for the lifecycle cost values to be comparable among different systems, their values are calculated with the use of a special purpose algorithm. Statistical analysis of the estimated cost values is then employed for assessing the flexibility of each manufacturing system. The method is applied in an industrial case for checking, also from a flexibility point of view, the investment on a production system, using real life industrial data.