special issue of IJPR on Lot sizing and scheduling (LSS)

@article{clark2011lot,
  title={Lot Sizing and Scheduling: Industrial extensions and research opportunities},
  author={Clark, A. and Almada-Lobo, B. and Almeder, C.},
  journal={International Journal of Production Research},
  volume={49},
  number={9},
  pages={2457--2461},
  year={2011},
  publisher={Taylor and Francis Ltd}
}

Editorial 
Lot sizing and scheduling: industrial extensions and research opportunities 


Production planning and scheduling seeks to efficiently allocate resources while fulfilling customer requirements and market demand, often by trading-off conflicting objectives. The decisions involved are typically operational (short-term) and tactical (medium-term) planning problems, such as work force levels, production lot sizes and the sequencing of production runs. 
Lot sizing seeks to determine the optimal timing and level of production. The early developments in this field have their roots in the Economic Order Quantity model developed by Harris (1913), extended some decades later by Wagner–Whitin (1958). Since then, researchers have developed successive generations of models combining capacitated and dynamic approaches, with a blurring of the boundaries between lot sizing and other research fields (Drexl and Kimms 1997, Karimi et al. 2003 --review: capacitated lot sizing). 
Most of the lot sizing literature is focused on discrete manufacturing. Currently, with changes in the philosophy of production planning and control, along with lean manufacturing processes and the shift from make-to-stock to make-to-order, there is a debate about whether or not lot sizing as a trade-off between setups and stocks is still an issue. Nonetheless, a high number of production processes are characterised by strong fluctuations of seasonal demand (with not enough capacity in some periods to process all the orders), by significant setup times and costs and by the economical advantage of holding stock rather than maintaining a capacity surplus. This is the case in process industries, where just-in-time systems cannot be implemented (Pochet 2001). As a result, process industries are a promising research area which is, in fact, addressed by the most recent papers on lot sizing and its extensions (Suerie 2005, Quadt and Kuhn 2008). 
The scheduling of production lots, as well as their sizing, is an area of increasing research attention within the wider field of production planning and scheduling. In many industrial applications, especially from the process industries, the close relationship between lot sizing and scheduling makes it imperative that both decisions are made simultaneously in order to efficiently use capacity. Traditional models have been increasingly refined to incorporate more detail and integrate lot sizing with scheduling. The current trend is also to couple lot sizing and scheduling with distribution, vehicle routing or cutting and packing decisions, etc. (Pochet and Wolsey 2006). 
Besides the integration of several ‘independent’ and previously self-contained research fields, researchers and practitioners worldwide have been trying to incorporate more specificities of the production environment in their models (Jans and Degraeve 2008 --review). Recent hot topics in the area include perishability, synchronisation of resources, non-triangular setups, time windows, and multiple stages with parallel machines. Nevertheless, there is a lack of research on the effect of using real life instances (some with ‘dirty data’) to carry out computational experiments, instead of relying on random instance generators, and on the integration of the algorithms with interactive decision support systems. 
 Naturally, increasing realism turns the mathematical models larger and more complex. 
This added complexity, and the need to increase the size of instances solvable to near- 
optimality, requires the integration of existing methods with novel and efficient 
optimisation algorithms, along with the development of tighter models and stronger 
valid inequalities based on the model polyhedral structures. Moreover, there is a 
continuing need to trade off the complexity of reality in planning models with 
mathematical and computational tractability. The research community is committed to 
the cross fertilisation between exact and approximate algorithms which exploit 
simultaneously the advantages of both methods (Jans and Degraeve 2007, Buschkuhl¨ 
et al. 2010 --review). Decomposition methods appear to be an intuitive way of separating the 
different sub-problems that are being integrated. Previous research on each separated 
problem can then be exploited. 
 This special issue is not the only evidence of a very active research community working 
on lot sizing related problems. Among the numerous publications, projects and meetings, 
we want to mention two recent representative activities. In May 2010 a three-year Marie 
Curie FP7 project of the European Union on ‘Industrial Extensions to Production 
Planning and Scheduling’ started, involving researchers from five institutions in Europe 
and Brazil. The outcome of this collaboration aims to be a set of mathematical models that 
effectively represent the production planning and scheduling challenges in a wide variety of 
industries, along with operationally viable and novel solution methods tested and 
validated with real data from a diverse range of industrial sectors: animal nutrition, pulp 
and paper, beverages, glass, dairy products, textiles, and furniture among others. (More 
information can be found at http://www.fe.up.pt/~ppext.) In July 2010 at the European 
Conference on Operational Research (EURO’10) in Lisbon, a stream on lot sizing was 
organised for the first time in the history of this conference, containing seven sessions with 
more than 25 talks. 
 This special issue of IJPR on Lot sizing and scheduling (LSS) aims to bring together 
much of the recent research from around the world, particularly that which addresses more 
realistic and practical variants of models, and the use of novel solution techniques. The 
integration of lot sizing and scheduling poses special challenges, and so pure scheduling 
papers were specifically excluded from the call. The papers in this special issue cover the 
range from applications in different industries to extensions of classical lot sizing 
approaches in different directions. It is evident that researchers are trying to incorporate 
more ‘real-world’ features such as production and delivery time windows, parallel 
machines, supply chain and reverse logistic aspects. Many of the papers also tackle 
different solution approaches ranging from exact dynamic programming methods for 
special cases to heuristic and metaheuristic algorithms. 
 The first section of this issue contains three articles devoted to applications in industry. 
Transchel et al. take inspiration from chemical industry data to test two alternative 
transportation-type reformulations of a multi-product LSS problem with 
sequence-dependent setup costs and times that combines discrete and continuous 
representations of time. Their results show significant improvements over a standard 
inventory and lot size (I&L) formulation. Hans and van de Velde tackle a real-world 
production planning problem arising in sand casting operations in metal foundries. The 
authors address the complexities when dealing with real data and all kinds of industrial 
hard and soft-constraints from a practical point of view. The overall problem can be seen 


----------------------- Page 4-----------------------


 International Journal of Production Research 2459 


as a generalisation of the capacitated parallel machine LSS. A three-step hierarchical 
planning approach solution procedure is embedded within a Decision Support System, 
involving mathematical programming and iterative local search improvements. Tang et al. 
use data and parameters from a Chinese steel complex to evaluate an improved 
Lagrangian Relaxation method to solve an integer programming model to decide which 
steel coils should be batched together in annealing furnaces, both statically and with a 
rolling horizon. 
 The two papers of the second section address the integration of consumption and 
recovery flows (NOT PRACTICAL). The lot sizing community has been driven by forward logistics, optimising 
lot sizes from the manufacturer to the customer. However, green or sustainable supply 
chains cannot neglect the impact of reverse logistics in running operations. Schulz studies 
the single-item dynamic lot sizing problem where returning products can be remanu- 
factured with separate setup costs. He proposes a generalisation of an existing Silver-Meal 
heuristic for static problems and then improves on its performance with a further heuristic, 
resulting in a halving of the percentage gap to the optimal solution. Kim and Goyal 
address a closed-loop single-manufacturer-single-retailer supply chain by integrating both 
consumption and recovery logistics. The authors analyse simultaneously from the 
manufacturer viewpoint the production lot size and the optimal recovery rate of used 
products, considering three types of recovery decisions: non-recovery, full-recovery and 
partial-recovery policies. The optimality domains of the three policies are assessed by 
means of a sensitivity analysis in the operational parameters of the problem. 
 The two papers of the third section are related to a recent family of problems, namely 
LSS with time windows (TW). (NOT INTERESTED) Traditionally, lot sizing problems consider dynamic 
demand within a finite planning horizon, without imposing any restriction on the 
production or delivery time frames. In the presence of production (delivery) TWs an order 
must be processed (delivered) within a given time interval. Absi et al. extend the single-item 
lot sizing problem with non-strictly included production TWs so that lost sales, backlogs 
and early production can be considered. The TW structure causes the zero-inventory 
ordering policy not to be valid anymore, but other useful properties are derived. They 
develop dynamic programming algorithms of complexity O(T2) to compute the optimal 


solutions. Akbalik and Penz address the single-item capacitated lot sizing problem coupled 
with TW deliveries. The flexibility gains of integrating production, transportation and 
storage decisions under different cost configurations and TW shipments are discussed. 
An exact MIP formulation and a new pseudo polynomial dynamic programming 
algorithm of complexity O(T2) are proposed. 


 The fourth section contains four papers which deal with parallel resources that 
complicate considerably the LLS underlying problem. Gicquel et al. tackle a difficult 
variant of the small-bucket discrete lot sizing and scheduling problem on identical parallel 
resources. The authors propose a family of strong valid inequalities that can be separated 
in polynomial time (INTERESTED), and which strengthen significantly the original MIP and enable 
instances of medium-size to be solved until optimality. Kaczmarczyk introduces new 
formulations based on integer variables (instead of binary variables) for the small-bucket 
proportional lot sizing and scheduling problem with identical parallel machines. By 
aggregating the machines, more compact formulations are possible which are advanta- 
geous when solving the problems. Haksoz¨ and Pinedo obtain new insights into the 
Economic Lot Scheduling problem about how setup costs and inventory carrying costs 
affect assignments of items to non-identical machines that operate at different speeds. 
Several models and practical heuristics are proposed based on different assumptions about 


----------------------- Page 5-----------------------


2460 Editorial 


the rotation schedules. Finally, Drechsel and Kimms study the cooperative capacitated lot 
sizing problem with common parallel resources and payable transshipments between 
players. The underlying idea is that each decision maker (player) can produce not only to 
meet own demand, but also to fulfill other players’ demand. The authors discuss the 
conflicting and hard objectives of minimising totals costs on the one hand and distributing 
stable and fair cost shares among players on the other hand. They suggest a minimax core 
costs allocation which is then modelled as a mathematical programme and solved using 
commercial optimisation software. 
 The final section of this special issue comprises two articles that are more focused on 
solution procedures, namely on exact and hybrid approaches, respectively. Glass and 
Possani tackle the lot streaming problem of multiple jobs in a flow shop. For two special 
cases, the problem with identical jobs and the two machine flow shop problem, the authors 
develop polynomial time algorithms for minimizing the makespan. Gonc¸ alves and Sousa 
address the economic lot scheduling problem (ELSP) for multiple products. They make 
use of a very flexible non-linear mixed-integer programme formulation to model initial 
inventories, backorders and setup times. They design a genetic algorithm determining the 
production sequence. The resulting production quantities are determined by using a 
standard LP-solver. 
 In total we received more than 50 submissions. We hope the articles selected for this 
special issue will be a source of latest research results on lot sizing and scheduling, 
stimulate the readers for this important area and provide a direction for future research. 
We are very grateful to all referees who have provided their constructive comments in 
order to improve the quality of the papers. We would like to thank the authors who have 
contributed their work in this special issue. 


References 


Buschkuhl,¨ L., Sahling, F., Helber, S., and Tempelmeier, H., 2010. Dynamic capaci- 
 tated lot-sizing problems: a classification and review of solution approaches. OR Spectrum, 
 32 (2), 231–261. 
Drexl, A. and Kimms, A., 1997. Lot sizing and scheduling – Survey and extensions. European 
 Journal of Operational Research, 99 (2), 221–235. 
Harris, F.W., 1913. How many parts to make at once. Factory: The Magazine of Management, 
 10 (2), 135–136. 
Jans, R. and Degraeve, Z., 2007. Meta-heuristics for dynamic lot sizing: a review and comparison of 
 solution approaches. European Journal of Operational Research, 177 (3), 1855–1875. 
Jans, R. and Degraeve, Z., 2008. Modeling industrial lot sizing problems: a review. International 
 Journal of Production Research, 46 (6), 1619–1643. 
Karimi, B., Fatemi Ghomia, S. M. T., and Wilson, J. M., 2003. The capacitated lot sizing problem: 
 a review of models and algorithms. Omega, 31 (5), 365–378. 
Pochet, Y., 2001. Mathematical Programming Models and Formulations for Deterministic 
 Production Planning Problems. Computational Combinatorial Optimization, Springer 
 Lecture Notes in Computer Science 2241. Springer. 
Pochet, Y. and Wolsey, LA., 2006. Production Planning Using Mixed Integer Programming. 
 Springer. 
Quadt, D. and Kuhn, H., 2008. Capacitated lot-sizing with extensions: a review. 4OR: A Quarterly 
 Journal of Operations Research, 6 (1), 61–83. 


----------------------- Page 6-----------------------


 International Journal of Production Research 2461 


Suerie. C., 2005, Time continuity in discrete time models: new approaches for production planning in 
 process industries , Lecture Notes in Economics and Mathematical Systems. Springer. 
Wagner, H. and Whitin, T., 1958. Dynamic version of the economic lot size model. Management 
 Science, 5 (1), 89–96. 


 Guest Editors 


 Alistair Clark 
 Department of Engineering Design and Mathematics 
 University of the West of England 
 United Kingdom 
 Email: alistair.clark@uwe.ac.uk 


 Bernardo Almada-Lobo 
 Department of Industrial Engineering and Management 
 Faculty of Engineering of University of Porto 
 Portugal 
 Email: almada.lobo@fe.up.pt 


 Christian Almeder 
 Department of Information Systems and Operations 
 Vienna University of Economics and Business 
 Austria 
 Email: christian.almeder@wu.ac.at