Economic lot scheduling with deliberated and controlled coproduction

This paper presents an algorithm to define the optimal parameters for deliberated and controlled coproduction in an economic lot scheduling problem setting (DCCELSP). Coproduction is said to be deliberated and controlled because it is possible to decide whether or not to coproduce when all the parameters associated with the process are known. The aim is to determine how to produce two products most economically where deliberated coproduction is an option. For this purpose, a procedure for defining optimal lot periods is introduced. Two models are proposed for this procedure and a numerical illustration is provided to gain insight into their dynamics. The cost advantages of coproduction were found to depend on the relationship between setup and holding costs, production rates, and demand for products. The more similar these system parameters are and the higher the machine usage ratio is, the more favourable coproduction is. Additionally, if coproduction is not deliberated appropriately, costs soar.     

Multi-level lot sizing and job shop scheduling with compressible process times: A cutting plane approach

This paper proposes an integer linear programming formulation for a simultaneous lot sizing and scheduling problem in a job shop environment. Among others, one of our realistic assumptions is dealing with flexible machines which enable the production manager to change their working speeds. Then, a number of valid inequalities are developed based on problem structures. As the valid inequalities can help in reducing the non-optimal parts of the solution space, they are dealt with as some cutting planes. The proposed cutting planes are used to solve the problem in (i) cut-and-branch, and (ii) branch-and-cut approaches. The performance of each cutting plane is investigated with CPLEX 12.2 on a set of randomly-generated test data. Then, some performance criteria are identified and the proposed cutting planes are ranked by TOPSIS method.     

Economic lot scheduling problem with imperfect production processes

In this paper, we model the effects of imperfect production processes on the economic lot scheduling problem (ELSP). It is assumed that the production facility starts in the in-control state producing items of high or perfect quality. However the facility may deteriorate with time and shifts at a random time to an out of control state and begins to produce nonconforming items. A mathematical model is developed for ELSP taking into account the effect of imperfect quality and process restoration. Numerical examples are presented to illustrate important issues related to the developed model.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

Production scheduling with alternative process plans

This paper deals with a scheduling problem with alternative process plans that was motivated by a production of wire harnesses where certain parts can be processed manually or automatically by different types of machines. Only a subset of all the given activities will form the solution, so the decision whether the activity will appear in the final schedule has to be made during the scheduling process. The problem considered is an extension of the resource constrained project scheduling problem (RCPSP) with unary resources, positive and negative time-lags and sequence dependent setup times. We extend classic RCPSP problem by a definition of alternative branchings, represented by the Petri nets formalism allowing one to define alternatives and parallelism within one data structure. For this representation of the problem, an integer linear programming model is formulated and the reduction of the problem, using time symmetry mapping, is shown. Finally, a heuristic algorithm based on priority schedule construction with an unscheduling step is proposed for the nested version of the problem and it is used to solve the case study of the wire harnesses production.     

Admission policies for the customized stochastic lot scheduling problem with strict due-dates

This papers considers admission control and scheduling of customer orders in a production system that produces different items on a single machine. Customer orders drive the production and belong to product families, and have family dependent due-date, size, and reward. When production changes from one family to another a setup time is incurred. Moreover, if an order cannot be accepted, it is considered lost upon arrival. The problem is to find a policy that accepts/rejects and schedules orders such that long run profit is maximized. This problem finds its motivation in batch industries in which suppliers have to realize high machine utilization while delivery times should be short and reliable and the production environment is subject to long setup times.We model the joint admission control/scheduling problem as a Markov decision process (MDP) to gain insight into the optimal control of the production system and use the MDP to benchmark the performance of a simple heuristic acceptance/scheduling policy. Numerical results show that the heuristic performs very well compared with the optimal policy for a wide range of parameter settings, including product family asymmetries in arrival rate, order size, and order reward.     

The stochastic economic lot scheduling problem: A survey

The present literature survey focuses on the stochastic economic lot scheduling problem (SELSP). The SELSP deals with the make-to-stock production of multiple standardized products on a single machine with limited capacity under random demands, possibly random setup times and possibly random production times. The main task of a production manager in this setting is the construction of a production plan for the machine. Based on the critical elements of such a production plan, we present a classification and extensive overview of the research on the SELSP together with an indication of open research areas. By doing so, we intend to stimulate the discussion on the important problems concerning the SELSP both from a theoretical and a practical point of view.     

Equivalence classes of problem instances for a continuous-time lot sizing and scheduling problem

In the context of a single machine, multi-item, continuous-time lot sizing and scheduling problem with a production rate alternating between the two values zero and full production rate, this paper identifies classes of equivalent problem instances which differ from one another in the way in which demand is represented. Each class contains an instance with a continuous cumulated demand function, and may contain demand functions with very different shapes, including functions with discontinuities. When approaching the problem (in order to solve it numerically, or to prove analytical results etc.), it therefore becomes possible to select, from many different representations, the problem instance which best meets the requirements of the applied method.     

A hybrid heuristic and linear programming approach to multi-product machine scheduling

A new heuristic approach is presented for scheduling economic lots in a multi-product single-machine environment. Given a pre-defined master sequence of product setups, an integer linear programming formulation is developed which finds an optimal subsequence and optimal economic lots. The model takes explicit account of initial inventories, setup times and allows setups to be scheduled at arbitrary epochs in continuous time, rather than restricting setups to a discrete time grid. We approximate the objective function of the model and solve to obtain an optimal capacity feasible schedule for the approximate objective. The approach was tested on a set of randomly generated problems, generating solutions that are on average 2.5% above a lower bound on the optimal cost. We also extend the approach to allow shortages.     

Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company

The aim of this work is to propose a solution approach for a capacitated lot sizing and scheduling real problem with parallel machines and shared buffers, arising in a packaging company producing yoghurt. The problem has been formulated as a hybrid Continuous Set-up and Capacitated Lot Sizing Problem (CSLP–CLSP). A new effective two stage optimisation heuristic based on the decomposition of the problem into a lot sizing problem and a scheduling problem has been developed. An assignment of mixture to buffers is made in the first stage, and therefore the corresponding orders are scheduled on the production lines by performing a local search. Computational tests have been performed on the real data provided by the company. The heuristic exhibits near-optimal solutions, all obtained in a very short computational time.     

Economic lot scheduling problem with imperfect production processes and setup times

Deteriorating production processes are common in reality. Although every production process starts in an ‘in-control’ state to produce items of acceptable quality, it may shift to an ‘out-of-control’ state, owing to ageing, at any random time and produce defective items. In the present article, we study the Economic Lot Scheduling Problem (ELSP) with imperfect production processes having significant changeovers between the products. The mathematical models are developed for the ELSP using both the common cycle approach and the time-varying lot sizes approach, taking into account the effects of imperfect quality and process restoration. Numerical examples are cited to illustrate the solution procedures and to compare the performances of the solution methodologies adopted to solve the ELSP.     

Discrete-time, economic lot scheduling problem on multiple, non-identical production lines

This paper deals with a general discrete time dynamic demand model to solve real time resource allocation and lot-sizing problems in a multimachine environment. In particular, the problem of apportioning item production to distinct manufacturing lines with different costs (production, setup and inventory) and capabilities is considered. Three models with different cost definitions are introduced, and a set of algorithms able to handle all the problems are developed. The computational results show that the best of the developed approaches is able to handle problems with up to 10000 binary variables outperforming general-purpose solvers and other randomized approaches. The gap between lower and upper bound procedures is within 1.0% after about 500 seconds of CPU time on a 2.66 Ghz Intel Core2 PC.     

A scheduling policy for adjusting economic lot quantities to a feasible solution

A heuristic scheduling policy is introduced for a multi-item, single-machine production facility. The scheduling policy uses the presumed optimal order quantities derived from solving an Economic Lot Size Problem and checks that the quantities obtain a feasible production schedule according to current inventory levels and expected demand rates. If not, the scheduling policy modifies the order quantities to achieve a possible solution without shortages. The scheduling policy is inspired by modification of the similar heuristic Dynamic Cycle Lengths Policy by Leachman and Gascon from 1988, 1991. The main characteristics of this scheduling policy are successive batches of the same item are treated explicitly, due to that it is quite possible that one item be manufactured several times before one other item is manufactured once more; the batches are ordered in increasing run-out time; if the existing situation creates stock-outs with ordinary order quantities, then the order quantities are decreased with a common scaling factor to try to prevent inventory shortages; in case the decrease of the order quantities changes expected run-out times, the batches are reordered after new run-out times; no filling up to an explicit inventory level is done, the filling up is done by the desirable order quantity; to prevent possible excess inventory the policy suggests time periods where no production should be performed. The scheduling policy contains no economical evaluation; this is supposed to be done when the order quantities are calculated, the policy prevents shortages and excess inventory. A numerical example illustrates the suggested scheduling policy. Finally, it is discussed as to how the policy can also take into account stochastic behaviour of the demand rates and compensate the schedule by applying appropriate safety times.     

A planning and scheduling model for onsertion in printed circuit board assembly

A planning and scheduling model is developed for the onsertion-phase in printed circuit board (PCB) assembly. PCBs are manufactured by machines that mount components, such as chips, on a PCB. On an onsertor machine, a certain number of component types can be stored. These components are subsequently used for the production of a certain PCB batch type. This research develops a production planning and scheduling formulation to determine the component–machine allocations, as well as a PCB sequence. Two strategies are proposed; one focusing on minimal number of changeovers (C-strategy), and the other on minimal process time (P-strategy). Both strategies were validated in a pilot study with real company data, with encouraging results for potential implementation.     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

Pattern scheduling

A pattern is a sequence of disjoint intervals on a circle together with fixed distances between these intervals. The intervals may be interpreted as tasks of a job which is produced perio-dically on one machine. How shouldr patterns be moved relative to each other to minimize the maximum overlapping of intervals (machines needed)? An enumerative procedure for solving this problem is given.     

A state-of-the-art review on scheduling with learning effects

Recently learning effects in scheduling have received considerable attention in the literature. All but one paper are based on the learning-by-doing (or autonomous learning) assumption, even though proactive investments in know how (induced learning) are very important from a practical point of view. In this review we first discuss the questions why and when learning effects in scheduling environments might occur and should be regarded from a planning perspective. Afterwards we give a concise overview on the literature on scheduling with learning effects.     

A Mixed Integer Linear Programming model for simultaneous design and scheduling of flowshop plants

Models representing batch plants, especially flowshop facilities where all the products require the same processing sequence, have received much attention in the last decades. In particular, plant design and production scheduling have been addressed as disconnected problems due to the tremendous combinatory complexity associated to their simultaneous optimization. This paper develops a model for both design and scheduling of flowshop batch plants considering mixed product campaign and parallel unit duplication. Thus, a realistic formulation is attained, where industrial and commercial aspects are jointly taken into account. The proposed approach is formulated as a Mixed Integer Linear Programming model that determines the number of units per stages, unit and batch sizes and batch sequencing in each unit in order to fulfill the demand requirements at minimum investment cost. A set of novel constraints is proposed where the number of batches of each product in the campaign is an optimization variable. The approach performance is evaluated through several numerical examples.     

An algorithm for the maximum revenue jobshop problem

In this paper, we state and study the problem of selecting a product mix and a dispatching rule for a jobshop system to maximize its revenue rate over an infinite planning horizon.