Scheduling of e-commerce packaging machines: blocking machines and their impact on the performance–waste tradeoff

Briskorn, Dirk; Boysen, Nils; Zey, Lennart Article — Published Version Scheduling of e-commerce packaging machines: blocking machines and their impact on the performance–waste tradeoff Journal of Scheduling Provided in Cooperation with: Springer Nature Suggested Citation: Briskorn, Dirk; Boysen, Nils; Zey, Lennart (2024) : Scheduling of e-commerce packaging machines: blocking machines and their impact on the performance–waste tradeoff, Journal of Scheduling, ISSN 1099-1425, Springer US, New York, NY, Vol. 28, Iss. 1, pp. 101-120, https://doi.org/10.1007/s10951-024-00826-9 This Version is available at: https://hdl.handle.net/10419/323370 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Journal of Scheduling (2025) 28:101–120 https://doi.org/10.1007/s10951-024-00826-9 Scheduling of e-commerce packaging machines: blocking machines and their impact on the performance–waste tradeoff Dirk Briskorn1·Nils Boysen2·Lennart Zey1 Accepted: 1 October 2024 / Published online: 25 October 2024 © The Author(s) 2024 Abstract To streamline their fulfillment processes, many e-commerce retailers today use automated packaging machines for their outbound parcels. An important performance–waste tradeoff is associated with these machines: To reduce packaging waste when handling different sized goods, packaging machines should be able to handle different carton sizes. However, more carton sizes lead to a more involved scheduling process, so that the throughput performance deteriorates (and vice versa). To investigate this tradeoff, this paper develops scheduling procedures for a specific type of packaging machine, called blocking machines. These packaging machines provide multiple back-to-back packaging devices, each continuously processing a dedicated carton size, but blocking each other whenever incoming goods are not properly ordered according to carton sizes on the infeed conveyor. To reduce the resulting throughput loss, we derive various scheduling problems for optimizing the inflow of goods, provide a thorough analysis of the computational complexity, and derive an exact dynamic programming approach that is polynomial in the number of orders to be packed. This allows us to solve even large real-world instances to proven optimality with which we can analyze the performance–waste tradeoff of blocking machines. Keywords E-commerce ·Packaging machines ·Environmental impact ·Scheduling 1 Introduction Because of the repetitive and physically demanding nature of warehouse work, many efforts have been made to reduce the burden on human workers. In addition to forklifts and conveyors, which have an even longer tradition, crane-operated high-bay warehouses, for example, have been assisting in the storage and retrieval of goods since the 1960s (Boysen and de Koster, 2024). Driven by the huge success of e-commerce, the last decades have seen further progress in the field of wareBNils Boysen [email protected] http://www.om.uni-jena.de Dirk Briskorn [email protected] http://www.prodlog.uni-wuppertal.de Lennart Zey [email protected] 1Bergische Universität Wuppertal, Professur für BWL, insbesondere Produktion und Logistik, Rainer-Gruenter-Str. 21, 42119 Wuppertal, Germany 2Friedrich-Schiller-Universität Jena, Lehrstuhl für Operations Management, Carl-Zeiß-Straße 3, 07743 Jena, Germany house automation (see Azadeh et al. 2019). Today, there are automated solutions for all basic warehousing functions (see Boysen et al. 2019): For example, there are mobile shelflifting robots for the transport function, autonomous mobile robots for picking rectangular goods from shelves, robotic arms with vacuum grippers for picking from bins, mobile robots with tiltable trays for order sorting, and industrial robots for palatalizing boxes and cartons. This paper deals with the automation of the packaging function, where the picked (and consolidated) products required by customer orders are either wrapped in plastic film or packed in cardboard boxes by a fully automated packaging machine. Machines for the latter case, which we focus on in this paper, are very common in e-commerce because cardboard boxes provide better protection, especially for fragile goods (Escursell et al., 2021). These machines are fed with goods and cardboard packaging material via a conveyor and a feeding shaft, respectively. Most machines include a cutting mechanism to reduce the size of the boxes to fit the orders. This avoids higher postage charges and excess fill material caused by unnecessarily large packages. The packaging material is then folded, sealed and labeled by the machine. Finally, the finished boxes are conveyed to the shipping area. 123 102 Journal of Scheduling (2025) 28:101–120 Fig. 1 Paper E-Com Fit of Hugo Beck with two back-to-back packaging devices (Source: Hugo Beck) In their packaging machine evaluation paper, Pfoser et al. (2021) report state-of-the-art throughput performance of up to 1000 packages per hour for single-piece orders. For multipiece orders, throughput is lower because their variety is still a greater technological challenge. However, since the majority of e-commerce orders are for a single item (the average number of items ordered at Amazon Germany, for example, is only 1.6, see Boysen et al. 2019), automated packaging machines are very common in today’s e-commerce fulfillment centers. There are several types of packaging machines, which we compare in more detail in Sect.2. One common setup that we will focus on in this paper is the blocking machine,shown in Fig.1. To avoid the disadvantages of setups where cartons must be changed on-the-fly whenever a different carton size is required, blocking machines use multiple downstream packaging devices, each of which is permanently associated with a specific carton size. These subsequent packaging devices are arranged back-to-back along the infeed conveyor, causing blockages whenever incoming goods are not properly ordered by size. Because goods cannot overtake each other on the infeed conveyor, a good that is assigned to an upstream packaging device will block subsequent goods that require a downstream device. Thus, one or multiple packaging slots in a packaging batch (i.e., the set of orders concurrently packed by all parallel packaging devices) remain empty and a blocking loss occurs. A suitable sequencing of orders within the infeed sequence can reduce the blocking loss and thus improve the throughput performance of a blocking machine. This directly leads to the following performance–waste tradeoff: More carton sizes to choose from reduces packaging waste, but also tends to increase the loss of throughput performance due to blockings. To explore the performance–waste tradeoff, this paper provides the following contributions: •We introduce a novel scheduling problem for blocking machines that minimizes blocking loss for different inflows of orders. For example, many e-commerce retailers equip their human pickers with multi-bin picking carts to collect completed orders in a sort-while-pick picking process (e.g., see De Koster et al. 2007). In this case, the inflow to a packing machine can be altered by changing the order in which these carts are processed and the order in which each cart’s orders are placed on the machine’s infeed conveyor. We describe alternative inflows and their effect on the scheduling problem in Sect.3. •We provide a thorough analysis of computational complexity for all resulting problem variants. This leads to an exact dynamic programming (DP) algorithm that is polynomial in the number of goods to be packed, once the number of carton sizes is fixed. This allows us to solve large instances of real-world size within very short runtimes to proven optimality. •With this algorithm in hand, we explore the performance– waste tradeoff of packaging machines. For a given number of carton sizes to be provided, we first optimize a suitable selection of specific carton sizes to minimize packaging waste. Then, we minimize the blocking loss by solving our scheduling problem for the selected carton sizes. This allows us to quantify packaging waste and throughput loss if different numbers of carton sizes are to be provided. This delivers decision support for warehouse managers who need to make the right choice of carton sizes. The rest of the paper is organized as follows. In Sect.2, we discuss related decision problems and review the literature. In Sect.3, we define the different variants of the packaging machine scheduling problem (PMSP) treated in this paper, which differ in the inflow of goods and the flexibility to reduce blocking loss by changing the processing sequence of orders. Section4contains a detailed analysis of the computational complexity, and Sect.5provides an efficient exact solution method based on DP. In Sect.6and Sect. 7we elaborate on our computational study and explore the performance–waste tradeoff. Finally, Sect.8concludes the paper. 2 Related decisions and literature review A recent in-depth survey paper on sustainability in ecommerce packaging (Escursell et al., 2021) and our own (thorough) literature search reveal that there is no previous research on packaging machine scheduling and its impact on the waste–performance tradeoff. However, in order to position our work in relation to previous research, we take a look at related decision tasks. Specifically, we address (i) the choice between different packaging machine setups, (ii) the choice of carton sizes, and (iii) the packing of goods into car123 Journal of Scheduling (2025) 28:101–120 103 Fig. 2 Alternatives to blocking machines. Left: Setup machine X7TM of Packsize requiring setups for carton size switches (Source: Packsize). Right: Parallel packing machines connected by a conveyor system (Source: Rovema) tons. Finally, we also discuss (iv) other scheduling problems with a similar problem structure. (i) Choice of packaging machine setups: Based on numerous site visits to e-commerce warehouses, a thorough evaluation of packaging machine manufacturers’ websites, and discussions with managers and consultants in the field, the authors are aware of two alternatives to blocking machines. Setup machines (see Fig. 2(left)) are equipped with an automated carton switching device. They automatically load the currently required carton size into the carton feeding shaft of their single packaging device and remove the old one. The resulting setups cannibalize packaging capacity and, thus, also create a waste–performance tradeoff. Since high-speed setups are mandatory for economical application of automated packaging, we were told that they are a common source of errors that require a lot of machine maintenance. On the positive side, setup machines do not require redundant hardware. To completely avoid the waste–performance tradeoff, multiple independent packaging machines, each dedicated to a specific carton size, can be used in parallel. These machines are accessed via switches from the main conveyor (see Fig.2(right)). Independent machines without carton size switches, however, require a high investment. Blocking machines can be seen as a compromise between these two alternatives. They use dedicated packaging devices without setups, but allow reuse of parts of the hardware. The price for this is a blocking loss if products and their demanded carton sizes are not properly sequenced in the infeed. In our research, we only address blocking machines and leave a more comprehensive evaluation of all different setups to future research. (ii) Choice of carton sizes: To achieve economies of scale in purchasing and to limit handling effort, retailers cannot provide a perfectly fitting carton for every product (or multi-piece order). Therefore, the number of carton sizes used is reduced to a few dozen at most. Typically, automated packaging demands an even smaller portfolio of carton sizes than manual packaging due to the higher flexibility of human work. Once the number of different carton sizes to be used is determined, choosing the specific sizes that minimize packaging waste for a given set of orders an optimization problem by itself. Heuristics based on clustering methods (Liu et al., 2013; Brinker and Gündüz, 2016) and genetic algorithms (Singh and Ardjmand, 2020) have been introduced. For our operational scheduling problem, we assume that the set of available carton sizes has already been decided in a previous (longterm) decision task. However, for our evaluation of the waste–performance tradeoff, we also determine the minimum waste carton sizes for a given set of orders to be packed (see Sect.7.1). To do so, we apply a straightforward DP approach, similar to the one proposed by Lee et al. (2015), which optimizes the height of crates in the chemical industry to accommodate a given set of goods. (iii) Packing of goods into cartons: The question of how to pack the goods of multi-piece orders into boxes is closely related to the bin packing problem. Surveys on this classic of the operations research domain are provided, for example, by Delorme et al. (2016) (exact algorithms) and Coffman et al. (2013) (heuristics). However, unlike bin packing, where all bins are the same size and the number of bins to pack all products must be minimized, e-commerce retailers have boxes of different sizes. Their choice is to determine the best box for each order jointly with the packing task, minimizing packaging waste and add-on volume. Fontaine and Minner (2023) proposes an efficient branch-and-repair method for this decision. For our scheduling problem, we assume that the choice of carton size into which each order is to be packed is already given. Recall that most orders for which automated packaging is applied are single-piece orders anyway, where the choice of the best-fitting carton size is trivial. (iv) Related scheduling problems: There is scheduling research for manufacturers of packaging machinery (e.g., (Adler et 123 104 Journal of Scheduling (2025) 28:101–120 al., 1993)) and for manufacturers of packaging materials (e.g., (Li et al., 2018)). However, we are not aware of any scientific scheduling research that specifically addresses e-commerce retailers and their use of packaging machinery to package their own goods. For setup machines, minimizing setup loss for a given order set on a single machine is a special case of the well-known traveling salesman problem (Burkard et al., 1998). For blocking machines, where the sizes of goods of each packaging batch must be properly ordered according to the subsequent packaging devices, such that the total number of packaging batches is minimized, this transformation is not available. Furthermore, unlike traditional machine scheduling, where the sequence in which orders are processed is typically unrestricted, e-commerce packaging machines are involved in a multi-stage process (e.g., including picking and order consolidation (Boysen et al., 2019)). The resulting material flow between these stages often relies on a batchwise transport (see Sect. 3.1), so the flexibility to sequence the inflow of goods is limited (i.e., only the sequence of batches and the order sequence per batch can be changed). Extensions of traditional machine scheduling to account for such limited flexibility in order sequencing are known as group technology. Machine scheduling adaptations for this type of inflow have been studied, for example, by Ng et al. (2005), Janiak et al. (2005), and Li et al. (2011). However, due to our completely different objective function these previous scheduling problems are not directly applicable. We conclude that our PMSP and its influence on the waste– performance tradeoff of packaging machines has not been addressed before. 3 Problem description To ease understanding of the variants of PMSP treated in this paper, we start with a verbal problem characterization, examples, and the discussion of our basic assumptions in Sect.3.1. Afterward, we provide a precise mathematical problem definition in Sect.3.2. 3.1 Problem characterization, examples, and assumptions The basic decision task of the PMSP is the sequence in which orders to be processed by the packaging machine are placed onto the machine’s infeed conveyor. Each order demands a specific carton size to be properly packed, which are provided by multiple subsequent packaging devices, arranged back-to-back along the conveyor. Since orders cannot overtake each other on the conveyor, it may occur that orders block each other. A blocking occurs whenever a preceding order demands a carton size provided by an anterior (or the same) packaging device, so that a subsequent order cannot reach its dedicated, yet blocked position along the belt. Thus, one or multiple packaging slots in a packaging batch (i.e., the set of orders concurrently packed by all parallel packaging devices) remain empty and a blocking loss occurs. A suitable sequencing of orders within the infeed sequence can reduce the blocking loss and thus improve the throughput performance of a blocking machine. The PMSP aims to minimize the number of packaging batches that are required to process all orders. Since packing is part of a multi-stage order fulfillment process, we are typically not completely free in the sequence orders are loaded into the packaging machine’s infeed sequence. Depending on the type of inbound stream, we face different levels of flexibility how to manipulate the infeed sequence. Many warehouses apply multi-bin picking carts, as depicted in Fig.3. Such a picking cart either accompanies a human picker during a picker-to-parts process. Each bin of a cart is then associated with a specific customer order, so that the picker can directly place each demanded product into the right customer bin in a sort-while-pick process (De Koster et al., 2007). Alternatively, picking carts are also applied to deliver orders from the consolidation stage, where products get sorted after picking in a sort-after-pick process (Boysen et al., 2019). In both cases, orders (each stored in a separate bin) arrive in picking carts at the infeed station of the packaging machine, where order after order is placed onto the infeed conveyor (either manually or by an automated solution). Based on this basic process, we differentiate the following types of inbound streams: •(a) Given cart sequence: The sequence in which the picking carts are processed at the infeed station can be given. This is, for instance, the result when processing the carts after the widespread first-come-first-served rule. Hence, only the sequence in which the orders of each subsequent cart are placed onto the conveyor is the lever to alter the packaging machine’s infeed sequence. Note that each cart must be completely processed before the next one can be started. •(b) Arbitrary cart sequence: Alternatively, next to the order sequence per cart also the sequence in which a given set of picking carts, waiting at the loading station, are processed can be part of the decision. Once the cart sequence is determined, again, each cart must be completely processed before the next one can be started. Nevertheless, this leaves more flexibility to improve the infeed sequence. •(c) Arbitrary infeed sequence: Finally, the largest flexibility is at hand if all orders of the given order set can 123 Journal of Scheduling (2025) 28:101–120 105 Fig. 3 Picking carts in a warehouse (Source: Lightning Pick) be brought into an arbitrary infeed sequence. This case arises if the current planning run only has to decide on the order sequence of a single picking cart or if incoming goods have been intermediately stored in a random access buffer (e.g., in an ASRS, see Boysen and Stephan, 2016). Note that other warehouses do not apply picking carts to deliver orders to packaging machines. If only single-piece orders are picked, then all demanded products can be placed into the same large bin. Order consolidation is not necessary, because it is known that each product refers to its own order. These bins with single-piece orders can also arrive at the infeed station, e.g., delivered by forklifts, AGVs, or on a conveyor. In relation to the cart-based process elaborated above, bins correspond to carts and products to orders. Although the physical process is different, it can be modeled by the same three types of inbound streams as elaborated above. Note, furthermore, that a fixed and given infeed sequence of orders, which cannot be altered (e.g., because it directly arrives from the picking area on a conveyor), leaves no optimization problem and is thus not considered in our problem differentiation. These alternative inbound streams offer different levels of flexibility to alter the infeed sequence. Exploring the impact of these flexibility levels (also including a fixed infeed sequence) on the waste–performance tradeoff is part of our computational study in Sect.7. Example 1 The basic input data of the example instance depicted in Fig.4a are four picking carts, denoted A, B, C, and D, each filled with two different orders. Each order’s demanded carton size is given by the white number within the respective gray order square. We have demanded carton sizes from 1 to 5, so that our packaging machine also has five back-to-back packaging devices each servicing one of the sizes. On the right side, we see two different infeed sequences (b) and (c). A given cart sequence leads to three packaging batches and a blocking loss of seven (see solution (b)). The relationship among these two performance measures is as follows: We have three batches with five packaging devices. This leads to 15 slots, among which eight are used by the given orders, whereas seven remain unused and constitute blocking loss. If the cart sequence is part of the decision, then optimal solution (c) leads to only two packaging batches and a blocking loss of 2 ·5−8=2. Example 2 Now, we consider the same situation as in Example 1, where, however, the managerial decision has been made to merely provide two carton sizes of size 3 and 5. Figure5d indicates the modified input data, where the actual sizes of the orders, which are equal to the sizes of Example 1, are indicated by the white subscripts within the gray order squares. Their assignment to the next larger available carton size is given by the (normal-sized) white numbers in the order squares. This induces a packaging waste of six, due to putting orders into cartons of larger size than is actually required. An optimal solution of PMSP, which does not improve if the cart sequence can be altered, is depicted in (e). Because we only have two carton sizes, we only require two back-toback packaging devices, which reduces the investment cost for the blocking machine. This, however, also implies less packaging capacity, so that we need five packaging batches (and thus have to accept a longer makespan until all orders are completed). Two packaging devices and five batches directly imply a blocking loss of 2·5−8=2 slots that remain empty, which is however no improvement compared to solution (c) of Example 1. We can deduce two issues for these two examples: (i) More sequencing flexibility (i.e., if the cart sequence is part of the decision and not given) as well as (ii) fewer carton sizes can but need not reduce the throughput loss. Before, we continue with a precise problem definition of our PMSP variants, we discuss the (simplifying) assumptions made in this paper to derive the PMSP in its very basic form: •We consider only a single packaging machine with fixed order assignments. When multiple parallel packaging machines are available, the order assignment is another relevant decision. Our solution methods can be applied to evaluate different order-machine assignments, but we leave the evaluation of such a decomposition approach to future research. 123 106 Journal of Scheduling (2025) 28:101–120 Fig. 4 Example 1of PMSP with and without given cart sequence Fig. 5 Example 2of PMSP with fewer carton sizes •For convenience, we neglect the potential impact of previous planning runs. That is, we neglect the possibility that the last orders of the preceding planning run could potentially share a packing batch with the first orders of the subsequent planning run. It is easy to relax this simplification, but we have chosen to stick with the simplest problem setup. •We assume that variable-speed conveyor segments ensure that orders arrive in the infeed sequence without gaps. Of course, the scheduling of packaging machines is particularly important when packaging is a bottleneck stage. In this case, gaps degrade the throughput of a bottleneck resource. Therefore, we assume that a retailer interested in PMSP has already eliminated this obvious source of wasted bottleneck capacity. If gaps exist, they could result in additional blocking loss despite properly sequenced orders approaching a blocking machine. We leave the consideration of gaps to future research. •We assume that each order requires a specific carton size. The additional flexibility provided by hierarchical compatibility, which allows orders to be packed in larger cartons than necessary to reduce throughput loss at the cost of additional waste, is thus neglected and left for future research. •Finally, we assume that all input data is known with certainty. Note that for a reliable automated packaging process, detailed size information about the arriving products must be available anyway, so this assumption does not seem to be a severe constraint in our case. Given this decision context, our PMSP is precisely defined in the following section. 3.2 Problem definition We consider a given set Jof orders, where each order j∈J has a (carton) size sj∈{1,...,S}and a cart (number) cj∈ {1,...,C}. Here, Sis the number of distinct sizes and Cis the number of carts. We assume that each size in {1,...,S} and each cart in {1,...,C}is related to at least one order (otherwise, we can reduce the number of sizes or the number of carts). Note that both, Sand C, are implied by Jand, thus, are given, as well. We denote the set of orders with cart number cas Jcand will say that order jis in cart cif j∈Jc. A solution is a permutation σof orders in J. We denote the k-th order in σby σ(k). A solution σis feasible if and only if for each pair of carts cand cwith c<ceither all orders with cart number cprecede all orders with cart number c in σor the other way around (if cart sequencing is part of the decision). Feasibility of a solution σ, thus, implies that orders appear clustered by cart numbers in σ. To evaluate a solution, we denote by (σ) =|{k|k= 1,...,|J|−1,sσ(k)≤sσ(k+1)}| the number of packaging batches of a solution, which equals the number of orders followed immediately by an order of larger or equal size in σ). We say that there is a break between positions kand k+1, if sσ(k)≤sσ(k+1), that is, if a new batch starts in position k+1. Because each packaging batch takes constant time for packing the orders at the subsequent packaging devices in parallel, we, then, associate (σ) with the makespan, that is, Cmax(σ) =(σ). The PSMP is to determine a solution that minimizes Cmax(σ) among all feasible solutions. While the special case of PSMP with C=1 covers the setting with an arbitrary infeed sequence (see Sect.3.1), the setting with a given infeed sequence is not covered by a special case of PSMP. Therefore, we define a variant of PSMP, 123 Journal of Scheduling (2025) 28:101–120 107 namely PSMP-fixed, to formalize this problem. PSMP-fixed has the same input as PSMP, the same solution space, and the same evaluation of solutions. A solution is considered feasible, however, if and only if for each pair of carts cand c with c<call orders with cart number cprecede all orders with cart number cin σ. We, thus, require that the given cart sequence has carts in increasing order of their numbers. The PSMP-fixed is to determine a solution that minimizes Cmax(σ) among all feasible solutions. 4 Analysis of computational complexity This section provides an in-depth analysis of computational complexity for PSMP and PSMP-fixed. For the former problem, we distinguish cases where the given number of carts is either C=1, Cis fixed to a given constant, or Cis part of the input. For both problems, the given number of carton sizes Scan either be fixed or is part of the input. Thus, we consider eight problem variants in total. We start with PSMP-fixed. We consider the greedy style algorithm sketched in the following. We assign orders in Jone by one to positions in the permutation in ascending order. For each position k, an order is assignable if it has not been assigned to a previous position yet and its cart number refers to the cart currently processed according to the given sequence. Let sbe the size of the order in position k−1if k>1, and s=∞otherwise. Let, furthermore, Jbe the set of available orders with sizes smaller than s.IfJ=∅, then we choose an order with maximum carton size among all available orders for position k. This implies a break between positions k−1 and k,ifk>1. If J=∅, then we choose an order with maximum size among orders in Jfor position k. This implies no break between positions k−1 and k,if k>1. We refer to this algorithm as GREEDY and introduce the following lemma related to it. Lemma 1 GREEDY achieves an optimum solution for PSMPfixed. Proof Consider an optimum solution σ∗and a further solution σobtained by GREEDY. Let k<|J|be the first position where σ∗and σdiffer. Note that if there is no such position σis optimum. Obviously, cσ∗(k)=cσ(k). We distinguish two cases regarding the sizes of σ∗(k)and σ(k). •If sσ∗(k)=sσ(k), then we can simply switch σ∗(k)and σ(k)in σ∗and obtain an optimum solution that equals σ up to position k. •If sσ∗(k)= sσ(k), we modify σ∗as follows. Let kbe the position where σ(k)is assigned to according to σ∗, that is σ∗(k)=σ(k). Note that k>k. We move σ∗(k)to position kand delay all orders in positions kto k−1 by one position. We refer to the modified solution as σ. Note that positions 1 to k−1 and k+1to|J|are not modified. Furthermore, between positions k+2 and k orders in σare in the same relative order as in σ∗. Hence, the total number of breaks immediately before the jobs in these positions is not higher in σthan in σ∗.Forthe consideration of positions kand k+1 we distinguish two cases in the following –Ifsσ∗(k)>sσ(k), then a break occurs in σ∗between k−1 and kbut no break occurs in σbetween k−1 and k, because sσ(k)is maximum among orders in J.This holds true if J=∅and among all available orders if J=∅. Hence, there is no break in σbetween k−1 and k. However, there is a break in σbetween kand k+1, because there is one in σ∗between k−1 and kand sσ(k)<sσ∗(k). So, the total number of breaks between k−1 and kand between kand k+1is1in both, σ∗and σ. –Ifsσ∗(k)<sσ(k), then a break occurs in σ∗between k−1 and kand a break occurs in σbetween k−1 and k, because GREEDY arranges a break only if J=∅. Then, there is a break in σbetween k−1 and kbecause there is one in σ. There is no break in σ between kand k+1, because sσ(k)>sσ∗(k). Hence, again the total number of breaks between k−1 and kand between kand k+1 is 1 in both, σ∗and σ. Hence, in both cases σis optimum, as well. Concluding, there is an optimum solution coinciding with σ up to position kand, by applying the argument in an iterative manner, σis optimum.  Now, we are able to easily verify that the infeed sequence in Fig.4b is indeed optimum for given cart sequence A,B,C,D], because it is the output of GREEDY. Regarding the computational complexity, the following theorem follows. Theorem 1 PSMP with a fixed number of carts and PSMPfixed can be solved in polynomial time. Proof We can evaluate each sequence of carts using GREEDY according to Lemma 1. It is easy to see that GREEDY runs in polynomial time and there is a fixed number C!of cart sequences and, hence, this procedure runs in polynomial time.  Recall that the case C=1 corresponds to an arbitrary infeed sequence as mentioned in Sect.3.1. Hence, PSMP with an arbitrary infeed sequence can be solved in polynomial time. Finally, we consider PSMP with a fixed number of carton sizes S. We start with the basic idea of the approach, which is to separate the decisions about breaks between orders of the same cart and those of consecutive carts in a solution. We refer to these types as internal breaks and external breaks.We 123 108 Journal of Scheduling (2025) 28:101–120 do so, by guessing the number Cs,sof carts with first order’s size sand last order’s size sfor each pair (s,s)of sizes in an optimum solution. We refer to a set of such numbers (one number for each pair (s,s)) as a size profile. Example 1(cont.): The size profiles corresponding to the solution depicted in Fig.4b and c, respectively, are specified as ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 00000 10000 00000 00200 01000 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ and ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ 00000 10001 00000 00200 00000 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ . For example, we have C4,3=2, because in both solutions there are two carts with first order’s size 4 and last order’s size 3. However, while the solution in Fig. 4b has a cart with first order’s size 5 and last order’s size 2 and, thus, C5,2=1, the solution in Fig.4c has no such cart. Thus, we have C5,2=0. We determine (i) the sequence of orders within each cart, such that there are exactly Cs,scarts with first order’s size sand last order’s size sand (ii) the sequence of carts, then, for each size profile. Note that both decisions together imply a feasible solution. Note, furthermore, that for taking the second decision only first order’s size and last order’s size of a cart are relevant. Hence, we can take the first decision irrespective of the second. The procedure, which we dub SIZE_PROFILE, enumerates all size profiles and determines (i) the sequence of orders within each cart and (ii) the sequence of carts as detailed below. We restrict ourselves to size profiles with (s,s)∈S×SCs,s=C. 1. To determine the sequence of orders within the each cart, we first determine the minimum number of internal breaks c,s,sbetween orders of cart c, if the first order’s size is sand the last orders size is s. We can use a straightforward adaption of GREEDY with C=1, where we have no freedom to decide the first and the last position and the corresponding orders are eliminated from the set of available orders. We refrain from giving a formal proof, because it is essentially the same as the proof for Lemma 1 (note that additionally k<|J|for the variant at hand). Hence, we can determine all c,s,svalues in polynomial time. Having determined c,s,sfor each cart cand pair of sizes (s,s), we now consider a bipartite graph G=(V,U,E) where nodes in V={1,...,C}correspond to carts and nodes in Ucorrespond to pairs of sizes. Exactly Cs,s nodes in Ucorrespond to pair (s,s). An edge between node c∈Vand a node in Ucorresponding to the pair of sizes (s,s)reflects cart cto have first order’s size sand last order’s size s(and exists only if ccan have first order’s Table 1 c,s,sfor each cart c and pair of sizes (s,s)in Example 1 (s,s)ABCD (1,2)–––1 (2,1)–––0 (3,4)–11– (4,3)–00– (2,5)1––– (5,2)0––– size sand last order’s size s). Choosing this edge in the following corresponds to choosing the sequence of orders for cart cimplying c,s,sinternal breaks determined by the adaption of GREEDY. Consequently, an edge between c∈Vand a node in Ucorresponding to pair of sizes (s,s) has weight c,s,s, and we determine a minimum weight perfect matching G. Such a matching implies a choice of a sequence of orders for each cart, which is in line with the given size profile and has a minimum number of internal breaks between orders of the same cart. Example 1(cont.): Table 1outlines c,s,sfor each cart cand each pair (s,s)of sizes of the instance depicted in Fig.4a. A numerical value is given only if ccan have first order’s size sand last order’s size s. Moreover, Fig.6 depicts bipartite graphs and highlights minimum weight perfect matchings for two size profiles of this instance instance. 2. To determine the sequence of carts, we propose a DP approach, where we construct the sequence by adding carts one by one to an existing sequence of carts. A state ( k,l)specifies the number ks,sof carts scheduled so far with first order’s size sand last order’s size sfor each pair (s,s)and the size lof the last order in the sequence. We have a transition from state ( k,l)to state ( k,l),if and only if exactly one number k s,sis increased by one as compared to ks,s, the others are identical, and the last size indicator l=sreflects that a cart corresponding to pair (s,s)has been added to the sequence. Transition costs are in {0,1}and reflect whether or not an external break occurs before the first order of the newly added cart. Note that this is implied by land the first order’s size s. Note, furthermore, that the DP approach does not differentiate carts with the same pair of first order’s size and last order’s size (as determined above). Each state is evaluated by the number of external breaks between carts so far. Theorem 2 PSMP can be solved in polynomial time, if the number of carton sizes is fixed. Proof SIZE_PROFILE evaluates each size profile following the above points 1. and 2. The number of size profiles is in O(CS2)and, thus, polynomial (for fixed S). For each size 123 Journal of Scheduling (2025) 28:101–120 115 Fig. 8 Runtime of DP in CPU seconds depending on the number of popular sizes Sand the number of jobs per cart |Jc| •High impact of the number of popular sizes S: The other influencing factor of the runtime of DP according to our theoretical analysis (see Sect.5.2) is the number of popular sizes S. Recall that only the (popular) sizes with the most orders per cart need to be considered. According to our computational results, their number increases, obviously, if we have more sizes S(i.e., more sizes increase the probability that more of them are popular), the size distribution is uniform (i.e., the triangular distribution produces a few highly demanded sizes, so that just a few become popular), and have small order capacity |Jc|per cart. Especially, the later effect seems to counter intuition, because more orders (and thus larger instance sizes) seem to induce shorter runtimes. The latter effect is further analyzed in Fig.8. Here, the runtimes for instances with C=20 carts and S=15 carton sizes are depicted as a function of the jobs per cart |Jc|and the total number of popular sizes Sover all carts. Note that the lower bound on Sis C, if each cart has exactly one popular size. In Fig.8, we restrict ourselves to values of S=25,...,34, because values out of this range are rare. Instances resulting in the same number of popular sizes Sare connected. In line with our theoretical runtime analysis of DP, we can observe that the runtimes remain (rather) stable for a constant number of popular sizes S, irrespective of the number of jobs per cart |Jc|. As expected, the runtimes seem to increase almost linearly with an increase of popular sizes S. Therefore, we can conclude that the counterintuitive result of Table 3(i.e., larger cart capacities |Jc|decrease runtime) can thus be explained by the fact that more orders with their respective sizes tend to decrease the amount of popular carton sizes Sof an instance. More random size selections for more orders on larger carts during data generation increases the probability that only a few of them will receive the highest demand and thus be popular. With only a few size selections, it is more likely that all sizes will have low demand and many of them will then be popular. We conclude that, consistent with our theoretical analysis, the runtime of DP for solving PSMP with arbitrary cart sequence is mainly driven by the number of carts Cand the number of popular sizes S. However, even for warehouses where these numbers take their maximum value, the runtime of DP is small. Thus, DP seems well suited to solve even large PSMP instances of real-world size to proven optimality. 7 Managerial issues This section is devoted to management issues. Specifically, we investigate the following three research tasks: (i) Once it has been decided how many different carton sizes should be available, the specific carton sizes need to be determined. To decide this important long-term issue, we use another DP approach to minimize the packaging waste for a given order set. Packaging waste arises by putting products into larger cartons than necessary to save on the number of employed carton sizes. With the DP, we can determine the packaging waste as a function of the number of available carton sizes. (ii) The complete waste–performance tradeoff of blocking machines is evaluated in Sect.7.2. Here, we investigate to what extent more carton sizes reduce packaging waste but increase the performance loss (and vice versa). We quantify the performance loss by the blocking loss defined in Sect.3, which counts the number of empty packing slots unused due to blocked packaging devices. (iii) Finally, Sect. 7.3 examines the value of sequencing flexibility. The two extremes are either no flexibility or full flexibility. In the former case, a fixed sequence of orders approaches the packaging machine without the possibility of changing it. Full flexibility (i.e., the given set of orders can be put into an arbitrary infeed sequence), on the other hand, promises the least performance loss, and inbound processes based on picking carts (with either a given or arbitrary cart sequence) lie somewhere in between the two extremes. We examine how switching to either of these inbound processes affects the throughput performance of a packaging machine. 7.1 What carton sizes to select? Prior to operational scheduling, which is the main focus of this paper, long-term decisions must be made regarding the available carton sizes. The design of the blocking machine (and the resulting investment cost) is mainly influenced by the number of carton sizes to be provided, since each additional carton size requires another packaging device. We provide decision support on the right number of carton sizes in Sect.7.2. There, we explore the waste–performance trade123 116 Journal of Scheduling (2025) 28:101–120 Fig. 9 Packaging machine during the carton folding process (Source: Sparck Technologies) off that is mainly driven by the number of available carton sizes. This section is dedicated to the choice of specific carton sizes, once the decision on the number of carton sizes to provide has already been made. If—based, for instance, on historical data—reliable information on the sizes of the orders to be packed and the frequency, in which each order size occurs, is available, then we can optimize the specific carton sizes, such that the total packaging waste gets minimized. Packaging machines fold the carton over the goods to be packed (see Fig.9) and cutting of the carton at a suitable position ensures that in flow direction no packaging waste occurs. Across the flow direction, however, packaging waste arises whenever a good is packed into a carton of excessive width. This reduces the min-waste problem to a one-dimensional problem that only decides on the width of the cartons to be provided. Once the orientation of the orders to be packed is given, the resulting optimization problem can easily be solved by a straightforward DP. Recall that a similar DP has already been introduced by Lee et al. (2015)for optimizing the height of crates in the chemical industry (see Sect.2). The DP proceeds as follows. We employ states (s,k), which define that carton size s∈ {1,...,S}is selected as the k-th carton size to be provided. For a given number of total carton sizes Kto select, we thus have O(|S|·K)states. We consider potential carton sizes from Sto 1. As a result, we have a single starting state (S,1) and a single dummy end state (0,K+1). A transition from state (s,k)to (s,k), with s<sand k=k+1, reflects that all order sizes having order size s≥sj>sget assigned to carton size s. For each of those orders, a packaging waste of s−sjoccurs. As a result, the cost c(s,s), associated with the transition, equal the sum of the resulting waste. Finally, we formulate the Bellman function as f(s,k)= min f(s,k−1)+c(s,s)|s>s. Clearly, this DP deterFig. 10 Example for the DP solving the min-waste policy Fig. 11 Packaging waste per number of carton sizes for the real-world dataset mines the minimum packaging waste for the given order sizes in polynomial time. Example 4 Based on the order data given in Example 1, Fig.10a presents the resulting input data for the min-waste policy. The resulting DP graph, if K=2 carton sizes are to be provided, is given in Fig.10b. The bold-marked optimal solution leads to two carton sizes of size 5 and 3, with a total waste of 6, which equals the situation in Example 2. Given this optimization approach, we can quantify the packaging waste for our real-world dataset (see Sect.6.1) depending on the number of carton sizes that are provided. The results are plotted in Fig.11. The performance metric reported here denotes the minimum waste determined by DP for the respective number of available carton sizes in relation to the waste if only a single one-size-fits-all carton is applied in %. The run times for applying the min-waste DP are near zero for every tested value of K, while it takes between 1.86s (K=1) and 16.79s (K=10) on average to apply the minwaste DP followed by solving the resulting instance by DP. These results lead us to our first managerial takeaway. Finding 1: More carton sizes can significantly reduce the amount of packaging waste. However, the positive impact of additional carton sizes quickly diminishes. Adding a second carton size more than halves the amount of packaging waste, but adding an additional carton size when more than a handful are already available hardly contributes to any further significant reduction. This is good news for packaging machine users: There is no need to have an excessive num123 Journal of Scheduling (2025) 28:101–120 117 ber of carton sizes. With just a handful of sizes, most of the possible waste reduction can be achieved. 7.2 The waste–performance tradeoff This section completes the picture on the waste–performance tradeoff and also includes the performance impact of the number of available carton sizes. Recall that more carton sizes tend to make it harder to properly sort the inbound orders according to demanded carton sizes on the infeed conveyor. Thus, more carton sizes not only promise a reduction of packaging waste—as the previous section has shown— but also tend to increase the blocking loss, where capacity is wasted and packaging slots must remain empty. More carton sizes come along with more back-to-back packaging devices that need to be installed along the infeed conveyor. Thus, more available carton sizes induce higher investment cost for the blocking machine and an increase of packaging capacity per packaging batch. To evaluate these expected coherences in our real-world data (i.e., solved with DP for the optimized carton sizes), Fig.12 relates the number of available carton sizes to the performance side of the waste–performance tradeoff. Specifically, these results relate to the following three basic performance metrics and how they are impacted by the number of available carton sizes, namely: (a) the makespan (i.e., defined by the number of packaging batches that are required to pack all orders), (b) the total blocking loss (i.e., defined by the total packaging capacity, obtained by multiplying the batches with the number of packaging devices, minus the number of orders), and (c) the blocking loss per packaging device (i.e., total blocking loss divided by the number of packaging devices). These results suggest the following findings: (a) Makespan: More carton sizes to choose from requires more back-to-back packing devices, each dedicated to a specific size. More devices increase the packaging capacity, so we can validate the expected effect that the makespan for processing the orders of the real-world dataset decreases with more carton sizes (see Fig.12a). However, their positive effect is diminishing, which is an indicator of the increasing difficulty of actually using the additional packaging capacity. (b) Total blocking loss: The increase in total blocking loss the more carton sizes are available is visualized in Fig.12b. Obviously, more and more packaging slots must remain empty because even our exact DP algorithm cannot properly sort the infeed sequence by carton size. (c) Blocking loss per packaging device: Each additional packaging device added by another carton size causes an additional amount of blocking loss per device, as shown in Fig.12c. We can see that the first additional carton sizes in particular lead to a significant increase in this performance metric. However, once a certain number of carton sizes are already available, each additional packaging device tends to add a fluctuating amount of blocking loss per device without a clear trend. By relating these performance metrics to the packaging waste examined in the previous section, the full waste–performance tradeoff can be visualized using Fig.13. Here, we show the efficient frontier for different numbers of available carton sizes in terms of both dimensions (i.e., waste and performance). Of course, the final choice of an appropriate number of carton sizes depends not only on these two dimensions, but also on the total cost of ownership of any additional packaging device. Because cost information varies widely among packaging machine manufacturers and can change over time, we will not include cost in our analysis. Instead, we end this section with the following take-home message: Finding 2: More carton sizes reduce packaging waste, but also lead to more blocking loss, where more and more packaging slots must remain empty because the back-to-back packaging devices cannot receive orders properly sequenced by size. However, both effects diminish quickly, so introducing just a few (i.e., a handful in our data) carton sizes can provide a good compromise in the waste–performance tradeoff. This is good news for e-commerce retailers because it helps keep the necessary investment in back-to-back packaging equipment at a manageable level. 7.3 The impact of sequencing flexibility Packing is just one stage of the complete order fulfillment process of warehouses and distribution centers. Before an order can be packed into a suitable carton, the ordered products must be retrieved either by a picker-to-parts or a parts-to-picker process (see De Koster et al. 2007, Lee et al. 2019). Depending on how these previous stages are connected to the infeed conveyor of a packaging machine, our PSMP faces different levels of sequencing flexibility (see also Sect.3.1). Basically, there are the following alternatives: (i) Fixed infeed sequence: No sequencing flexibility for our PSMP is available, if the preceding stages are directly connected by a conveyor that is fixedly attached to the infeed of the packaging machine. In this case, the infeed sequence equals the processing sequence of the previous stages, which is typically not optimized according to the needs of the packaging stage. We emulate this case by determining ten random order sequences for each instance of our real-world dataset, which cannot be altered by our PSMP. Their results are averaged. (ii) Given cart sequence: The order transport between the preceding stages and packaging can also be organized in 123 118 Journal of Scheduling (2025) 28:101–120 Fig. 12 Performance impact of different number of available carton sizes a batchwise manner, e.g., via picking carts or bins. If the arrival sequence of these transport batches is given, the PSMP with given cart sequence is to be solved, and there remains the flexibility to optimize the infeed sequence of orders per cart. The add sequencing flexibility promises less blocking loss compared to (i) but comes at the price of double handling. The orders must be retrieved in a specific sequence from their batches to properly place them on the infeed conveyor. This produces extra search effort and manual handling. We emulate this case by drawing ten random cart sequences per instance, solving each of the resulting PSMP-fixed instances with GREEDY to optimality, and averaging the results. (iii) Arbitrary cart sequence: Even more flexibility is offered, if also the sequences in which the batches (carts) are processed is part of the optimization by solving PSMP with arbitrary cart sequence. On top of the double handling, this also increases the demand for shop floor space for the intermediate storage of the batches. We emulate this case by solving PSMP with arbitrary cart sequence for each real-world instance. (iv) Perfect infeed sequence: Finally, blocking loss can be avoided to the largest possible extent, if a random access on the complete order set is possible at the infeed station of the packaging machine. This either requires additional hardware (e.g., an automated storage and retrieval system (ASRS)) or excessive manual labor to retrieve the orders in arbitrary sequence from various batches. We emulate this case, by adding all orders to a single cart and solving the resulting instance with GREEDY (see Sect.4). Since it seems almost impossible to quantify the cost of these alternatives in an objective and generalizable way, we focus Fig. 13 Efficient frontier of different numbers of available carton sizes and their impact on packing waste and blocking loss only on the performance impact of additional sequencing flexibility. In Fig.14, we relate the makespan of alternatives (i), (ii), and (iii) to that of alternative (iv) and denote this performance metric ’increase in makespan in %’. The run times for (i), (ii), (iii) and (iv) are 0.17s, 0.28s, 17.6s and 0.6s on average. The average results for our real-world dataset show that a fixed infeed sequence that does not account for blocking loss of the packaging machine wastes a lot of packaging capacity and leads to an increase in makespan of more than 200% compared to the perfect infeed sequence. The performance loss of a batch transport to the packaging stage is much smaller, which leads us to the final managerial takeaway of this paper. 123 Journal of Scheduling (2025) 28:101–120 119 Fig. 14 Performance impact of sequencing flexibility Finding 3: Batch transport of orders to the packing stage promises a good compromise between the higher investment cost of more sophisticated solutions based on random order access on all orders and the excessive blocking loss of given infeed sequences. Especially if the transport batches are not too small, this is still true if the batches are processed on a first-come, first-served basis based on a given cart sequence. 8 Conclusions This paper focuses on the scheduling of e-commerce packaging machines. Specifically, we are the first to address the peculiarities of blocking machines, where multiple back-toback packaging devices provide access to packaging cartons of different sizes. For various types of inflows, this paper defines the resulting order scheduling problem such that blocking loss (i.e., wasted packaging slots that cannot be utilized because the orders to be packed are not properly ordered according to carton sizes on the infeed conveyor) is minimized. We provide an in-depth analysis of the computational complexity and provide exact solution methods that provide optimal solutions in a runtime polynomial in the number of orders. Our performance analysis shows that these algorithms can solve even largest instances of real-world size to proven optimality in less than a minute. In addition, we investigate management issues and summarize the results into three main management takeaways. From a theoretical perspective, future research should address the open case and resolve the complexity status of PSMP with arbitrary cart sequence when the number of carton sizes is part of the input. From a practical perspective, future research should systematically compare blocking machines with other types of packaging machines (e.g., setup machines) in terms of the waste–performance tradeoff. The latter, in particular, could make a valuable contribution to successfully reducing the environmental burden of excessive packaging waste in e-commerce. Funding Open Access funding enabled and organized by Projekt DEAL. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecomm ons.org/licenses/by/4.0/. References Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J. C., & Wu, T. P. (1993). BPSS: A scheduling support system for the packaging industry. Operations Research, 41(4), 641–648. Azadeh, K., De Koster, R., & Roy, D. (2019). Robotized and automated warehouse systems: Review and recent developments. Transportation Science, 53(4), 917–945. Boysen, N., & de Koster, R. (2024). 50 years of warehousing research— An operations research perspective. European Journal of Operational Research.https://doi.org/10.1016/j.ejor.2024.03.026 Boysen, N., De Koster, R., & Weidinger, F. (2019). Warehousing in the e-commerce era: A survey. European Journal of Operational Research, 277(2), 396–411. Boysen, N., & Stephan, K. (2016). A survey on single crane scheduling in automated storage/retrieval systems. European Journal of Operational Research, 254(3), 691–704. Brinker, J., & Gündüz, H. I. (2016). Optimization of demand-related packaging sizes using a p-median approach. The International Journal of Advanced Manufacturing Technology, 87, 2259–2268. Burkard, R. E., Deineko, V. G., Van Dal, R., van der Veen, J. A., & Woeginger, G. J. (1998). Well-solvable special cases of the traveling salesman problem: A survey. SIAM Review, 40(3), 496–546. Coffman, E. G., Csirik, J., Galambos, G., Martello, S., & Vigo, D. (2013). Bin Packing Approximation Algorithms: Survey and Classification. In P. M. Pardalos, D.-Z. Du, & R. L. Graham (Eds.), Handbook of Combinatorial Optimization (pp. 455–531). Springer. https://doi.org/10.1007/978-1-4419-7997-1_35 De Koster, R., Le-Duc, T., & Roodbergen, K. J. (2007). Design and control of warehouse order picking: A literature review. European Journal of Operational Research, 182(2), 481–501. Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1), 1–20. Escursell, S., Llorach-Massana, P., & Roncero, M. B. (2021). Sustainability in e-commerce packaging: A review. Journal of Cleaner Production, 280, 124314. Fliedner, M., Boysen, N., & Scholl, A. (2011). On the part inventory model sequencing problem: Complexity and beam search heuristic. Journal of Scheduling, 14, 17–25. Fontaine, P., & Minner, S. (2023). A branch-and-repair method for three-dimensional bin selection and packing in e-commerce. Operations Research, 71(1), 273–288. 123 120 Journal of Scheduling (2025) 28:101–120 Janiak, A., Kovalyov, M. Y., & Portmann, M.-C. (2005). Single machine group scheduling with resource dependent setup and processing times. European Journal of Operational Research, 162(1), 112– 121. Lee, S. J., Chew, E. P., Lee, L. H., & Thio, J. (2015). A study on crate sizing problems. International Journal of Production Research, 53(11), 3341–3353. Li, X., Gao, L., Pan, Q., Wan, L., & Chao, K.-M. (2018). An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 49(10), 1933–1945. Li, S., Ng, C. T., & Yuan, J. (2011). Group scheduling and due date assignment on a single machine. International Journal of Production Economics, 130(2), 230–235. Liu, Y., Wang, Z., & Cheng, G. Q. (2013). Optimization design for size of footwear outer packaging boxes. Advanced Materials Research, 694, 3516–3521. Ng, C. T., Cheng, T. E., Janiak, A., & Kovalyov, M. Y. (2005). Group scheduling with controllable setup and processing times: Minimizing total weighted completion time. Annals of Operations Research, 133(1–4), 163–174. Olist, (2019) . Brazilian e-commerce public dataset by olist. https:// www.kaggle.com/datasets/olistbr/brazilian-ecommerce (last access: January 2024). Pfoser, S., Brandner, M., Herman, K., Steinbach, E., Brandtner, P., & Schauer, O. (2021). Sustainable transport packaging: Evaluation and feasibility for different use cases. LOGI-Scientific Journal on Transport and Logistics, 12(1), 159–170. Singh, M., & Ardjmand, E. (2020). Carton set optimization in ecommerce warehouses: A case study. Journal of Business Logistics, 41(3), 222–235. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123