OR-Instances

Authors: Gregor Selinka, Raik Stolletz, Thomas I. Maindl

Published: Selinka, G., Stolletz, R., and T. I. Maindl (2022): Performance approximation of time-dependent queues with generally distributed abandonments. INFORMS Journal on Computing, 34 (19), 20–38

Abstract: Many stochastic systems face a time-dependent demand. Especially in stochastic service systems, for example in call centers, customers may leave the queue if their waiting time exceeds their personal patience. As discussed in the extant literature, it can be useful to use general distributions to model such customer patience. This paper analyzes the time-dependent performance of a multi-server queue with a non-homogeneous Poisson arrival process with a time-dependent arrival rate, exponentially distributed processing times, and generally distributed time to abandon. Fast and accurate performance approximations are essential for decision support in such queueing system, but the extant literature lacks appropriate methods for the setting we consider. To approximate time-dependent performance measures for small- and medium-sized systems, we develop a new stationary backlog-carryover (SBC) approach which allows for the analysis of underloaded and overloaded systems. Abandonments are considered in two steps of the algorithm: i) in the approximation of the utilization as a reduced arrival stream and ii) in the approximation of waiting-based performance measures with a stationary model for general abandonments. To improve the approximation quality, we discuss an adjustment to the interval lengths. We present a limit result which indicates convergence of the method for stationary parameters. The numerical study compares the approximation quality of different adjustments to the interval length. The new SBC approach is effective for instances with small numbers of time-dependent servers and Gamma-distributed abandonment times with different coefficients of variation and for an empirical distribution of the abandonment times from real-world data obtained from a call center. A discrete-event simulation benchmark confirms that the SBC algorithm approximates the performance of the queueing system with abandonments very well for different parameter configurations.

Data set: The data set contains all problem instances that are solved and discussed in Sections 4.2–4.4 of the numerical study of this paper. Related to the instances of the figures, we state the input parameters (arrival rate, abandonment rate, number of servers, processing rate) per interval. In addition,  we specify the parameter of the distribution for Gamma-distributed abandonment times (related to Figures 19–22).

SBC approach in Jupyter Notebook: The SBC algorithm is implemented in Python for a time-dependent number of servers and Gamma-distributed patience time (Section 4.4). 

Download: The zip file contains an Excel file with the data sets for the instances and the implementation of the SBC algorithm in Jupyter Notebook.

Authors: Sophie Weiss, Justus Arne Schwarz, Raik Stolletz
Forthcoming in: Weiss, S., J. A. Schwarz, and R. Stolletz (2019): The Buffer Allocation Problem in production lines: Formulations, solution methods, and instances. IISE Transactions (formerly IIE Transactions), 51 (5), 456–485.

Abstract: Flow production lines with finite buffer capacities are used in practice for mass production, e.g., in the automotive and food industries. The decision regarding the allocation of buffer capacities to mitigate throughput losses from stochastic processing times and unreliable stations is known as the Buffer Allocation Problem (BAP). This paper classifies and reviews the literature on the BAP with respect to different versions of the optimization problem. It considers the detailed characteristics of the flow lines, the objective function, and the constraints. Moreover, a new classification scheme for solution methods is presented that differentiates between explicit solutions, integrated optimization methods, and iterative optimization methods. The characteristics of test instances derived from realistic cases and test instances used in multiple references are discussed. The review reveals gaps in the literature regarding the considered optimization problems and solution methods, especially with a view on realistic lines. In addition, a library, “FlowLineLib”, of realistic and already used test instances is provided.

Data set: The  database FlowLineLib contains XML files for references that solve the BAP for models of realistic and popular test instances used in multiple references. The XML files capture all parameters of the optimized lines, including the parameters of the used probability distributions. If available, we also provide the suggested buffer allocations and their resulting objective values.

The test instances can be downloaded by clicking on the author names.

BAPs solved for models of realistic flow lines:

Chiang, S.-Y., Kuo, C.-T., & Meerkov, S. M. (2000). DT-bottlenecks in serial production lines: Theory and application. IEEE Transactions on Robotics and Automation, 16(5), 567–580.

Cochran, J. K., Kokangul, A., & Khaniyev, T. A. (2009). Stochastic approximations for optimal buffer capacity of many-station production lines. International Journal of Mathematics in Operational Research, 1(1/2), 211–227.

Kuo, C.-T., Lim, J.-T., & Meerkov, S. M. (1996). Bottlenecks in serial production lines: A system-theoretic approach. Mathematical Problems in Engineering, 2(3), 233–276.

Li, J. (2013). Continuous improvement at Toyota manufacturing plant: Applications of production systems engineering methods. International Journal of Production Research, 51(23–24), 7235–7249.

Mak, K. L. (1986). The allocation of interstage buffer storage capacity in production lines. Computers \& Industrial Engineering, 10(3), 163–169.

Matta, A., Pezzoni, M., & Semeraro, Q. (2012). A Kriging-based algorithm to optimize production systems approximated by analytical models. Journal of Intelligent Manufacturing, 23(3), 587–597.

Savsar, M., & Choueiki, M. H. (2000). A neural network procedure for Kanban allocation in JIT production control systems. International Journal of Production Research, 38(14), 3247–3265.

Tempelmeier, H. (2003). Practical considerations in the optimization of flow production systems. International Journal of Production Research, 41(1), 149–170.

Popular test instances:

Alon, G., Kroese, D. P., Raviv, T., & Rubinstein, R. Y. (2005). Application of the Cross-Entropy Method to the Buffer Allocation Problem in a simulation-based environment. Annals of Operations Research, 134(1), 137–151.

Altiok, T., & Stidham Jr., S. (1983). The allocation of interstage buffer capacities in production lines. IIE Transactions, 15(4), 292–299.

Can, B., Beham, A., & Heavey, C. (2008). A comparative study of genetic algorithm components in simulation-based optimisation. In Proceedings of the 2008 Winter Simulation Conference (pp. 1829–1837). Miami, FL, USA.

Can, B., & Heavey, C. (2011). Comparison of experimental designs for simulation-based symbolic regression of manufacturing systems. Computers & Industrial Engineering, 61(3), 447–462.

Can, B., & Heavey, C. (2012). A comparison of genetic programming and artificial neural networks in metamodeling of discrete-event simulation models. Computers & Operations Research, 39(2), 424–436.

Chan, F. T. S., & Ng, E. Y. H. (2002). Comparative evaluations of buffer allocation strategies in a serial production line. International Journal of Advanced Manufacturing Technology, 19(11), 789–800.

Chow, W.-M. (1987). Buffer capacity analysis for sequential production lines with variable process times. International Journal of Production Research, 25(8), 1183–1196.

Colledani, M., Matta, A., Grasso, M., & Tolio, T. (2004). A new analytical method for buffer space allocation in production lines. In 37th CIRP international seminar on manufacturing systems (pp. 231–237). Budapest, Hungary.

Conway, R., Maxwell, W., McClain, J. O., & Thomas, L. J. (1988). The role of work-in-process inventory in serial production lines. Operations Research, 36(2), 229–241.

Demir, L., Tunali, S., & Løkketangen, A. (2011). A tabu search approach for buffer allocation in production lines with unreliable machines. Engineering Optimization, 43(2), 213–231.

Dolgui, A., A. Eremeev, A. Kolokolov, & V. Sigaev. (2002). A genetic algorithm for the allocation of buffer storage capacities in a production line with unreliable machines. Journal of Mathematical Modelling and Algorithms, 1 (2), 89–104.

Dolgui, A., Eremeev, A. V., & Sigaev, V. S. (2007). HBBA: Hybrid algorithm for buffer allocation in tandem production lines. Journal of Intelligent Manufacturing, 18(3), 411–420.

Gershwin, S. B., & Goldis, Y. (1996). Efficient algorithms for transfer line design. Technical report, Massachusetts Institute of Technology.

Gershwin, S. B., & Schor, J. E. (2000). Efficient algorithms for buffer space allocation. Annals of Operations Research, 93(1), 117–144.

Harris, J. H., & Powell, S. G. (1999). An algorithm for optimal buffer placement in reliable serial lines. IIE Transactions, 31(4), 287–302.

Helber, S., Schimmelpfeng, K., Stolletz, R., & Lagershausen, S. (2011). Using linear programming to analyze and optimize stochastic flow lines. Annals of Operations Research, 182(1), 193–211.

Ho, Y. C., Eyler, M. A., & Chien, T. T. (1979). A gradient technique for general buffer storage design in a production line. International Journal of Production Research, 17(6), 557–580.

Jafari, M.A. & Shanthikumar, J.G., 1989. Determination of optimal buffer storage capacities and optimal allocation in multistage automatic transfer lines. IIE Transactions, 21(2), 130–135.

Köse, S. Y., Demir, L., Tunalı, S., & Eliiyi, D. T. (2015). Capacity improvement using simulation optimization approaches: A case study in the thermotechnology industry. Engineering Optimization, 47(2), 149–164.

Kolb, O., & Göttlich, S. (2015). A continuous buffer allocation model using stochastic processes. European Journal of Operational Research, 242(3), 865–874.

Kose, S. Y., & Kilincci, O. (2015). Hybrid approach for buffer allocation in open serial production lines. Computers & Operations Research, 60, 67–78.

Lambrecht, M., & Segaert, A. (1990). Buffer stock allocation in serial and assembly type of production lines. International Journal of Operations & Production Management, 10(2), 47–61.

Lee, H.-T., Chen, S.-K., & Chang, S. (2009). A meta-heuristic approach to buffer allocation in production line. Journal of C.C.I.T, 38(1), 167–178.

Liu, C.-M., & Sanders, J. L. (1988). Stochastic design optimization of asynchronous flexible assembly systems. Annals of Operations Research, 15(1), 131–154.

Lutz, C.M., Davis, K.R. & Sun, M., 1998. Determining buffer location and size in production lines using tabu search. European Journal of Operational Research, 106(2–3), 301–316.

Massim, Y., Yalaoui, F., Amodeo, L., Chatelet, E., & Zeblah, A. (2010).  Efficient combined immune-decomposition algorithm for optimal buffer allocation in production lines for throughput and profit maximization. Computers \& Operations Research, 37(4), 611–620.

Matta, A. (2008). Simulation optimization with mathematical programming representation of discrete event systems. In Proceedings of the 2008 Winter Simulation Conference (pp. 1393–1400). Miami, FL, USA.

McClain, J. O., & Moodie, D. R. (1991). A comment on “Buffer space allocation in automated assembly lines.” Operations Research, 39(5), 857–860.

Nahas, N., Ait-Kadi, D., & Nourelfath, M. (2006). A new approach for buffer allocation in unreliable production lines. International Journal of Production Economics, 103(2), 873–881.

Narasimhamu, K. L., Venugopal Reddy, V., & Rao, C. S. P. (2015). Optimization of Buffer Allocation in Manufacturing System Using Particle Swarm Optimization. International Review on Modelling and Simulations (IREMOS), 8(2), 212.

Nori, V. S., & Sarker, B. R. (1998). Optimum number of Kanbans between two adjacent stations. Production Planning \& Control, 9(1), 60–65.

Ouazene, Y., A. Yalaoui, F. Yalaoui, & H. Chehade. (2014). Non-Linear Programming Method for Buffer Allocation in Unreliable Production Lines. In Lecture Notes in Computer Science, Analytical and Stochastic Modeling Techniques and Applications, edited by B. Sericola, M. Telek, and G. Horváth, 80–94. Springer International Publishing

Papadopoulos, H. T., Heavey, C., & O’Kelly, M. E. J. (1989). Throughput rate of multistation reliable production lines with inter station buffers: (I) Exponential Case. Computers in Industry, 13(3), 229–244.

Papadopoulos, H. T., & Vidalis, M. I. (2001). A heuristic algorithm for the buffer allocation in unreliable unbalanced production lines. Computers & Industrial Engineering, 41(3), 261–277.

Papadopoulos, H. T., & Vouros, G. A. (1997). A model management system (MMS) for the design and operation of production lines. International Journal of Production Research, 35(8), 2213–2236.

Park, T. (1993). A two-phase heuristic algorithm for determining buffer sizes of production lines. International Journal of Production Research, 31(3), 613–631.

Pichitlamken, J., & Nelson, B. L. (2003). A combined procedure for optimization via simulation. ACM Transactions on Modeling and Computer Simulation, 13(2), 155–179.

Powell, S. G., & Pyke, D. F. (1996). Allocation of buffers to serial production lines with bottlenecks. IIE Transactions, 28(1), 18–29.

Sabuncuoglu, I., Erel, E., & Gocgun, Y. (2006). Analysis of serial production lines: characterisation study and a new heuristic procedure for optimal buffer allocation. International Journal of Production Research, 44(13), 2499–2523.

Seong, D., Chang, S. Y., & Hong, Y. (1995). Heuristic algorithms for buffer allocation in a production line with unreliable machines. International Journal of Production Research, 33(7), 1989–2005.

Sheskin, T. J. (1976). Allocation of interstage storage along an automatic production line. AIIE Transactions, 8(1), 146–152.

Shi, C., & Gershwin, S. B. (2009). An efficient buffer design algorithm for production line profit maximization. International Journal of Production Economics, 122(2), 725–740

Shi, C., & Gershwin, S. B. (2011). The segmentation method for long line optimization. In Proceedings of the 8th international conference on Stochastic Models of Manufacturing and Service Operations (pp. 128–135). Kusadasi, Turkey.

Shi, C., & S. B. Gershwin (2013). The Additive Property in Long Line Optimization. In IFAC Conference on Manufacturing Modelling, Management, and Control, (pp. 754–759). St. Petersburg, Russia.

Shi, L., & Men, S. (2003). Optimal buffer allocation in production lines. IIE Transactions, 35(1), 1–10.

Smith, J. M., & Chikhale, N. (1995). Buffer allocation for a class of nonlinear stochastic knapsack problems. Annals of Operations Research, 58(5), 323–360.

Smith, J. M., & Daskalaki, S. (1988). Buffer space allocation in automated assembly lines. Operations Research, 36(2), 343–358.

So, K. C. (1997). Optimal buffer allocation strategy for minimizing work-in-process inventory in unpaced production lines. IIE Transactions, 29(1), 81–88.

Soyster, A. L., Schmidt, J. W., & Rohrer, M. W. (1979). Allocation of buffer capacities for a class of fixed cycle production lines. AIIE Transactions, 11(2), 140–146.

Spinellis, D. D., & Papadopoulos, C. T. (2000). A simulated annealing approach for buffer allocation in reliable production lines. Annals of Operations Research, 93(1), 373–384.

Spinellis, D. D., & Papadopoulos, C. T. (2000). Stochastic algorithms for buffer allocation in reliable production lines. Mathematical Problems in Engineering, 5(6), 441–458.

Staley, D. R., & Kim, D. S. (2012). Experimental results for the allocation of buffers in closed serial production lines. International Journal of Production Economics, 137(2), 284–291.

Stolletz, R., & Weiss, S. (2013). Buffer allocation using exact linear programming formulations and sampling approaches. In IFAC Conference on Manufacturing Modelling, Management, and Control (pp. 1451–1456). St. Petersburg, Russia.

Tezcan, T., & Gosavi, A. (2001). Optimal buffer allocation in production lines using an automata search. In Proceedings of the 2001 Institute of Industrial Engineering Research Conference. Dallas, TX, USA.

Vergara, H. A., & Kim, D. S. (2009). A new method for the placement of buffers in serial production lines. International Journal of Production Research, 47(16), 4437–4456.
 
Vouros, G. A., & Papadopoulos, H. T. (1998). Buffer allocation in unreliable production lines using a knowledge based system. Computers & Operations Research, 25(12), 1055–1067.

Wang, H., & Wang, H.-P. (1991). Optimum number of Kanbans between two adjacent workstations in a JIT system. International Journal of Production Economics, 22(3), 179–188.

Weiss, S., A. Matta, & R. Stolletz (2017): Optimization of buffer allocations in flow lines with limited supply. Forthcoming in, IISE Transactions, DOI 10.1080/24725854.2017.1328751

Weiss, S., & Stolletz, R. (2015). Buffer allocation in stochastic flow lines via sample-based optimization with initial bounds. OR Spectrum, 37(4), 869–902.

Wellman, M. A., & Gemmill, D. D. (1995). A genetic algorithm approach to optimization of asynchronous automatic assembly systems. International Journal of Flexible Manufacturing Systems, 7(1), 27–46.

Yuzukirmizi, M., & Smith, J. M. (2008). Optimal buffer allocation in finite closed networks with multiple servers. Computers & Operations Research, 35(8), 2579–2598

Authors: Emilio Zamorano, Annika Becker, Raik Stolletz

Published: Journal of Scheduling, 21 (1), 93–109

Abstract: This paper addresses a task assignment problem encountered by check-in counter personnel at airports. The problem consists of assigning multiskilled agents to a sequence of tasks in check-in counters. Because each task's ending time is fixed to comply with the flight schedule, its processing time depends on the arrival of the assigned agents. We propose a mixed-integer program and a branch-and-price algorithm to solve this problem. We exploit the problem structure to efficiently formulate the pricing problems and improve computation time. Using real-world data from a German ground-handling agency, we conduct numerical studies to evaluate the performance of the proposed solutions.

Data set: The data set contains 4 realistic but not real instances for the task assignment problem with start time-dependent processing times problem. Each problem instance consists of a set of tasks, traveling times, and a set of agents. Detailed results for the problem instances are given in the Appendix of the paper.

Download:TAP Instances Zamoranoetal2016.zip

Authors: Alexander Lieder, Raik Stolletz

Published: Transportation Research Part E: Logistics and Transportation Review 88, 167–188.

Abstract: This paper presents an optimization method for the aircraft scheduling problem with general runway configurations. Take-offs and landings have to be assigned to a runway and a time while meeting the sequence-dependent separation requirements and minimizing the costs incurred by delays. Some runways can be used only for take-offs, landings, or certain types of aircraft while schedules for interdependent runways have to consider additional diagonal separation constraints.

Our dynamic programming approach solves realistic problem instances to optimality within short computation times. In addition, we propose a rolling planning horizon heuristic for large instances that returns close-to-optimal results.

Data set: The data set contains all problem instances that are solved and discussed in the numerical study of this paper. Each problem instance consists of a set of aircraft (with target times and operation classes) and class-dependent separation times for operations on the same runway and on interdependent runways. Optimal objective values of the problem instances are given in the Appendix of the paper.

Download: Dataset_LiederStolletz2016.xlsx