Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

A two pass heuristic algorithm for scheduling ‘blocked out’ units in continuous process industry

This paper addresses the problem of scheduling cascaded ‘blocked out’ continuous processing units separated by finite capacity storage tanks. The raw materials for the product lines arrive simultaneously on the input side of the first unit. But every unit can process only one product line at a time, thus giving rise to the possibility of spillage of raw material due to limited storage capacity. The need to process multiple product lines and the added constraint of multiple intermediate upliftment dates aggravate the problem. This problem is quite common in petrochemical industry. The paper provides a MINLP (Mixed Integer Non-Linear Programming) formulation of the problem. However, for any realistic scheduling horizon, the size of the problem is too large to be solved by standard packages. We have proposed a depth first branch and bound algorithm, guided by heuristics, to help planners in tackling the problem. The suggested algorithm could output near optimal solutions for scheduling horizons of 30 time periods when applied to real life situations involving 3 units and 3 product lines. Preliminary version of the paper appeared in the proceedings of MISTA, 2005.     

Opportunity-based age replacement with a one-cycle criterion

In this paper age replacement (AR) and opportunity-based age replacement (OAR) for a unit are considered, based on a one-cycle criterion, both for a known and unknown lifetime distribution. In the literature, AR and OAR strategies are mostly based on a renewal criterion, but in particular when the lifetime distribution is not known and data of the process are used to update the lifetime distribution, the renewal criterion is less appropriate and the one-cycle criterion becomes an attractive alternative. Conditions are determined for the existence of an optimal replacement age T^* in an AR model and optimal threshold age T_opp^* in an OAR model, using a one-cycle criterion and a known lifetime distribution. In the optimal threshold age T_opp^*, the corresponding minimal expected costs per unit time are equal to the expected costs per unit time in an AR model. It is also shown that for a lifetime distribution with increasing hazard rate, the optimal threshold age is smaller than the optimal replacement age. For unknown lifetime distribution, AR and OAR strategies are considered within a nonparametric predictive inferential (NPI) framework. The relationship between the NPI-based expected costs per unit time in an OAR model and those in an AR model is investigated. A small simulation study is presented to illustrate this NPI approach.     

Joint-optimization of inventory policies on a multi-product multi-echelon pharmaceutical system with batching and ordering constraints

This paper presents a methodology to find near-optimal joint inventory control policies for the real case of a one-warehouse, n-retailer distribution system of infusion solutions at a University Medical Center in France. We consider stochastic demand, batching and order-up-to level policies as well as aspects particular to the healthcare setting such as emergency deliveries, required service level rates and a new constraint on the ordering policy that fits best the hospital’s interests instead of abstract ordering costs. The system is modeled as a Markov chain with an objective to minimize the stock-on-hand value for the overall system. We provide the analytical structure of the model to show that the optimal reorder point of the policy at both echelons is easily derived from a simple probability calculation. We also show that the optimal policy at the care units is to set the order-up-to level one unit higher than the reorder point. We further demonstrate that optimizing the care units in isolation is optimal for the joint multi-echelon, n-retailer problem. A heuristic algorithm is presented to find the near-optimal order-up-to level of the policy of each product at the central pharmacy; all other policy parameters are guaranteed optimal via the structure provided by the model. Comparison of our methodology versus that currently in place at the hospital showed a reduction of approximately 45% in the stock-on-hand value while still respecting the service level requirements.     

Integrated production scheduling and distribution planning in dairy supply chain by hybrid modelling

In this paper we address the production scheduling and distribution planning problem in a yoghurt production line of the multi-product dairy plants. A mixed integer linear programming model is developed for the considered problem. The objective function aims to maximize the benefit by considering the shelf life dependent pricing component and costs such as processing, setup, storage, overtime, backlogging, and transportation costs. Key features of the model include sequence dependent setup times, minimum and maximum lot sizes, overtime, shelf life requirements, machine speeds, dedicated production lines, typically arising in the dairy industry. The model obtains the optimal production plan for each product type, on each production line, in each period together with the delivery plan. The hybrid modelling approach is adopted to explore the dynamic behavior of the real world system. In the hybrid approach, operation time is considered as a dynamic factor and it is adjusted by the results of the simulation and optimization model iteratively. Thus, more realistic solutions are obtained for the scheduling problem in yoghurt industry by using the iterative hybrid optimization-simulation procedure. The efficiency and applicability of the proposed model and approach are demonstrated in a case study for a leading dairy manufacturing company in Turkey.     

Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times

A modified flow-shop scheduling problem for a production system, characterized by parts machining followed by their subsequent assembly (joining) operation, is studied. Several products of different kinds are ordered. Each part for the products is processed on machine M₁ (the first stage) and then processed on machine M₂ (the second stage). Each product is processed (e.g., joined) with the parts by one assembly operation on assembly stage M_A (the third stage). The objective function to be minimized is the weighted sum of product completion times. The decision variables are the sequence of products to be assembled and the sequence of parts to be processed. In this paper, we assume that if product h is assembled before product h^′, then, on each machine, processing of any part for product h^′ is done after processing of all parts for product h is completed. We call this assumption “Assumption B(2)” and call this problem “SP_constrained”. An efficient solution procedure using a branch and bound method is developed based on this assumption, where Johnson's algorithm is used as a part of the solution procedure. Computational experiments are provided to evaluate the performance of the solution procedure. It has been found that the proposed solution procedure is effective to obtain an optimal or ε-optimal solution for larger-scaled problems. We further compare the optimal value for SP_constrained with the optimal value for another problem SP_{unconstrained} defined without Assumption B(2); the optimal solution for SP_{unconstrained} being significantly more difficult to obtain. We offer three propositions to analyze some special cases in which the difference between the optimal value of SP_constrained and the optimal value of SP_{unconstrained} is zero. For general cases, we make some computational experiments to evaluate the difference between the optimal value of SP_constrained and the optimal value of SP_{unconstrained}. It has been found that the difference is very small.     

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.     

Scheduling production of multiple part-types in a system with pre-known demands and deterministic inactive time intervals

We introduce and formalise a scheduling problem that consists in determining an optimum policy (i.e. one that minimises total inventory holding costs) to produce n part-types using a system that is able to share its capacity at all times among these part-types and that switches between an active and an inactive state for pre-known periods of time. Consequently, when active the system must produce enough reserves to meet the demand during the inactive interval. We show that there is always a simple optimum policy in which the production of the part-types is prioritised and, provided the units are properly defined, the optimum priority ordering corresponds to a non-decreasing sequence of the unit holding costs of the part-types.     

Inventory problems with perishable items: Fixed lifetimes and backlogging

Our model deals with a single-product and a single-stock location with Poisson demand. The replenishment leadtime from the external supplier is fixed. The lifetime of the product is also fixed, and aging is assumed to begin when the order is placed. When the age of a unit has reached its lifetime, the unit is useless and thus discarded from the system. The replenishment policy is assumed to be an order-up-to S-policy. Demand that cannot be met immediately is backordered. We consider three different cases where the service requirements are represented by: (1) backorder costs per unit, (2) a service level constraint, (3) backorder costs per unit and time unit. Cases 1 and 2 are solved exactly, while an approximation is developed for case 3. We show how the results from an earlier paper assuming lost sales can be used to solve the considered problems. Our results are compared to the results in a related paper considering (Q, r)-policies.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

Preventive maintenance in a 1 out of n system: The uptime,downtime and costs

In repairable systems with redundancy, failed units can be replaced by spare units in order to reduce the system downtime. The failed units are sent to a repair shop or manufacturer for corrective maintenance and subsequently are returned for re-use. In this paper we consider a 1 out of n system with cold standby and we assume that repaired units are “as good as new”.When a unit has an increasing failure rate it can be advantageous to perform preventive maintenance in order to return it to its “as good as new” state, because preventive maintenance will take less time and tends to be cheaper. In the model we present we use age-replacement; a machine is taken out for preventive maintenance and replaced by a standby one if its age has reached a certain value, T_pm. In this paper we derive an approximation scheme to compute the expected uptime, the expected downtime and the expected costs per time unit of the system, given the total number of units and the age-replacement value, T_pm. Consequently the number of units and the value T_pm can be determined for maximum long-term economy.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

Single machine common flow allowance scheduling with controllable processing times

In this paper, we consider single machine SLK due date assignment scheduling problem in which job processing times are controllable variables with linear costs. The objective is to determine the optimal sequence, the optimal common flow allowance and the optimal processing time compressions to minimize a total penalty function based on earliness, tardiness, common flow allowance and compressions. We solve the problem by formulating it as an assignment problem which is polynomially solvable. For some special cases, we present an O(n logn) algorithm to obtain the optimal solution respectively.     

An efficient approach for solving the lot-sizing problem with time-varying storage capacities

We address the dynamic lot size problem assuming time-varying storage capacities. The planning horizon is divided into T periods and stockouts are not allowed. Moreover, for each period, we consider a setup cost, a holding unit cost and a production/ordering unit cost, which can vary through the planning horizon. Although this model can be solved using O(T³) algorithms already introduced in the specialized literature, we show that under this cost structure an optimal solution can be obtained in O(T log T) time. In addition, we show that when production/ordering unit costs are assumed to be constant (i.e., the Wagner–Whitin case), there exists an optimal plan satisfying the Zero Inventory Ordering (ZIO) property.     

Optimal scheduling of batch industrial facilities

An increasing interest in batch processing has been evident in recent years. This renewed interest is explained by the inherent flexibility of such plants that permits a high level of response to uncertain market conditions and requirements. This level of response does require the use of efficient tools to help the decision-making process at the design and operational level. This paper presents a Mixed Integer Linear Program (MILP) model to optimise the scheduling of batch facilities subject to changeovers and distribution constraints so as to guarantee a pre-defined objective. Such an objective can be defined as the minimum orders' total lateness or the maximum distribution units loading capacity, among others. A continuous-time representation is used as well as the concept of job predecessor and successor to effectively handle changeovers. Facilities having non-identical parallel units/lines, sequence-dependent orders, finite release times for units and orders, restrictions on the suitability of jobs to lines/units and different possible destinations to available distribution units are also considered. Based on these characteristics the proposed model is able to determine the optimal allocation of jobs to production lines/units, the sequence of jobs on every line/unit and the starting and completion production times of each order. Also, the usage and allocation of the distribution resources (eg trucks) to orders and destinations are obtained based on their availability and suitability to the orders. The model led to the development of a prototype information system that can be used as a tool to help the decision-making process at the operational plant level.Finally, the applicability of the proposed system/formulation is shown through the resolution of an industrial real case where the production of polymers is performed.     

A complex discrete warm standby system with loss of units

A redundant complex discrete system is modelled through phase type distributions. The system is composed of a finite number of units, one online and the others in a warm standby arrangement. The units may undergo internal wear and/or accidental external failures. The latter may be repairable or non-repairable for the online unit, while the failures of the standby units are always repairable. The repairability of accidental failures for the online unit may be independent or not of the time elapsed up to their occurrence. The times up to failure of the online unit, the time up to accidental failure of the warm standby ones and the time needed for repair are assumed to be phase-type distributed. When a non-repairable failure occurs, the corresponding unit is removed. If all units are removed, the system is then reinitialized. The model is built and the transient and stationary distributions determined. Some measures of interest associated with the system, such as transition probabilities, availability and the conditional probability of failure are achieved in transient and stationary regimes. All measures are obtained in a matrix algebraic algorithmic form under which the model can be applied. The results in algorithmic form have been implemented computationally with Matlab. An optimization is performed when costs and rewards are present in the system. A numerical example illustrates the results and the CPU (Central Processing Unit) times for the computation are determined, showing the utility of the algorithms.     

Managing variances in manufacturing system design

The goal of this paper is to investigate how uncertainties in demand and production should be incorporated into manufacturing system design problems. We examine two problems in manufacturing system design: the resource allocation problem and the product grouping problem. In the resource allocation problem, we consider the issue of how to cope with uncertainties when we utilize two types of resources: actual processing capacity and stored capacity (inventory). A closed form solution of the optimal allocation scheme for each type of capacity is developed, and its performance is compared to that of the conventional scheme where capacity allocation and inventory control decisions are made sequentially. In the product grouping problem, we consider the issue of how we design production lines when each line is dedicated to a certain set of products. We formulate a mathematical program in which we simultaneously determine the number of production lines and the composition of each line. Two heuristics are developed for the problem.     

Single machine group scheduling with resource dependent setup and processing times

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.