Abstracts:Supply chain network design (SCND) is a large and growing area of research. Although SCND has a remarkable effect on companies’ main financial accounts, our examination reveals that most of the models only investigate roughly the costs and revenues related to the design project and neglect other significant financial factors linked to its future performance. This study carries out a comprehensive survey of SCND articles published from 2008 to 2021 by systematically selecting 689 journal papers and exploring their types, paradigms, modelling methods, and uncertainty factors, with special attention to financial considerations. We develop a framework to classify and analyse all these aspects. We also analyse the most recent survey studies related to SCND models, notably facility location problems (FLPs), hub location problems (HLPs), reverse logistics (RL), and closed-loop supply chains (CLSC). Compared to these studies, a broad range of topics is added to the search process. We recommend a framework for detecting and reporting financial perspectives by employing useful concepts, e.g., the duality principle, charts of accounts, and financial statements analysis. We identify several research gaps and offer future research directions such as using specific complementary equations, e.g., depreciation, amortisation, and inventory valuation, to improve the applicability of the SCND models.

Abstracts:Operations Research practitioners often want to model complicated functions that are difficult to encode in their underlying optimisation framework. A common approach is to solve an approximate model, and then use a simulation to evaluate the true objective value of one or more solutions. We propose a new approach to integrating simulation into the optimisation model itself. The idea is to run the simulation at each incumbent solution to a master problem. The simulation results are then used to guide the trajectory of the optimisation model itself using logic-based Benders cuts. We test the approach on a class of stochastic resource allocation problems with monotonic performance measures. We derive strong novel Benders cuts that are provably valid for all problems of the given form. We consider two concrete examples: a nursing home shift scheduling problem, and an airport check in counter allocation problem. While previous papers on these applications could only approximately solve realistic instances, we are able to solve them exactly within a reasonable amount of time. Moreover, while those papers account for the inherent variance of the problem by including estimates of the underlying random variables as model parameters, we are able to compute sample-average approximations to optimality with up to 100 scenarios.

Abstracts:This paper deals with the cyclic job shop problem where the task durations are uncertain and belong to a polyhedral uncertainty set. We formulate the cyclic job shop problem as a two-stage robust optimization model. The cycle time and the execution order of tasks executed on the same machines correspond to the here-and-now decisions and have to be decided before the realization of the uncertainty. The starting times of tasks corresponding to the wait-and-see decisions are delayed and can be adjusted after the uncertain parameters are known. In the last decades, different solution approaches have been developed for two-stage robust optimization problems. Among them, the use of affine policies, row and row-and-column generation algorithms are the most common. In this paper, we propose a branch-and-bound algorithm to tackle the robust cyclic job shop problem with cycle time minimization. The algorithm uses, at each node of the search tree, a robust version of the Howard’s algorithm to derive a lower bound on the optimal cycle time. Moreover, we design a row generation algorithm and a column-and-row generation algorithm and compare it to the branch-and-bound method. Finally, encouraging preliminary results on numerical experiments performed on randomly generated instances are presented.

Abstracts:We study single-machine scheduling problems involving a rate-modifying activity and two competing agents with due-date-related functions. Classical scheduling models assume that job processing times remain constant over time; however, in real-world settings, processing times may change due to factors such as technological upgrades or machine maintenance. We complement this with the notion of multiple independent agents competing over the use of a shared resource, each with their own motives. These considerations allow us to model the upcoming trend of the sharing economy, where resources are shared amongst independent competitors in the market. We aim to model these scenarios by considering a variety of scheduling criteria for each agent, including the makespan, the number of late jobs, and the total late work. To account for the change in processing times, we consider an optional rate-modifying activity that once completed, results in a reduction in subsequent job processing times. We show that problems involving the total late work are binary NP-hard and propose efficient pseudo-polynomial dynamic programming algorithms for solving these problems. We also show that the remaining problems are solvable in polynomial time.

Abstracts:We consider a Markov Decision Process (MDP), over a finite or infinite horizon, augmented by so-called (σ,ρ)-burstiness constraints. Such constraints, which had been introduced within the framework of network calculus, are meant to limit some additive quantity to a given rate over any time interval, plus a term which allows for occasional and limited bursts. We introduce this class of constraints for MDP models, and formulate the corresponding constrained optimization problems. Due to the burstiness constraints, constrained optimal policies are generally history-dependent. We use a recursive form of the constraints to define an augmented-state model, for which sufficiency of Markov or stationary policies is recovered and the standard theory may be applied, albeit over a larger state space. The analysis is mainly devoted to a characterization of feasible policies, followed by application to the constrained MDP optimization problem. A simple queuing example serves to illustrate some of the concepts and calculations involved.

Abstracts:This paper addresses an extension of the flexible job-shop scheduling problem where transportation resources are explicitly considered when moving jobs from one machine to another. Operations should be assigned to and scheduled on machines and vehicles and the routes of vehicles should be determined. We extend the classical disjunctive graph model to include transportation operations and exploit the graph in an integrated approach to solve the problem. We propose a metaheuristic using a neighborhood function that allows a large set of moves to be explored. As the exact computation of the makespan of every move is time-consuming, we present a move evaluation procedure that runs in constant time (which does not depend on the size of the instance) to choose a promising move in the neighborhood of a solution. This move evaluation procedure is used in a tabu search framework. Computational results show the efficiency of the proposed approach, the quality of the move evaluation procedure and the relevance of explicitly modeling transportation resources. New benchmark instances are also proposed.

Abstracts:In this work, we present a method that applies Deep Reinforcement Learning, an approximate dynamic programming procedure using deep neural networks, to the job shop scheduling problem (JSSP). The aim is to show that a greedy-like heuristic trained on a subset of problems, can effectively generalize to some extent to unseen instances, and be competitive compared to other methods. We model the JSSP as a Markov Decision Process and we exploit the efficacy of reinforcement learning to solve the problem. We adopt an actor-critic scheme based on policy gradients, specifically the Proximal Policy Gradient method, where the action taken by the agent is influenced by policy considerations on the state-value function. The procedures take into account the challenging nature of JSSP, where the state and the action space change for every instance and after each decision. To tackle this variability, we introduced a novel model based on two incident Long-Short Term Memory networks, followed by an encoding model, different in structure for both the actor and the critic. Experiments show the algorithm reaches good solutions in a short time, proving that is possible to generate new greedy heuristics just from learning-based methodologies. We compared our algorithms against several established heuristics, an adaptive method, a commercial solver based on branch and cut, and another approach based on Deep Reinforcement Learning, proving the validity of the proposed method in terms of time and makespan. The model can generalize, to some extent, to larger problems originating from a different distribution.

Abstracts:In this paper, we build a decision model to explore an innovative firm’s budget allocation problem, which needs to be solved for each successive generation of a product. The firm introduces the product to the market through a distributor while aiming to maximize the market potential. This goal can be achieved by investing in R&D and increasing availability using subsidies registered to the distributor. We analyze the problem using a game theoretical model and provide a guideline for the funding strategy. We show that the optimal budget allocation decision is characterized by two budget thresholds and a threshold on the cost efficiency of R&D. We identify and analyze the effects of two significant parameters, total available budget and efficiency level of R&D, on the optimal solution. In addition, we assess the model’s applicability by examining the expected excess budget requirement and the distributor’s expected profit. We provide valuable managerial insights on when and how to prioritize the two components of the budget.

Abstracts:When determining store locations, competing retailers must take customers’ store choice into consideration. Customers predominantly select which store to visit based on price, accessibility, and convenience. Incumbent retailers can estimate the weight of these factors (customer attraction parameters) using granular historical data. Their location decision under full information and simultaneous competition translates into an integer programming game. Unlike incumbents, new entrants lack this detailed information; however, they can observe the resulting location structure of incumbents. Assuming the observed location structure is (near-)optimal for all incumbent retailers, a new entrant can use these observations to estimate customer attraction parameters. To facilitate this estimation, we propose an “inverse optimization approach” for integer programming games (IPGs), enabling a new entrant to identify parameters that lead to the observed equilibrium solutions. We solve this “inverse IPG” via decomposition by solving a master problem and a subproblem. The master problem identifies parameter combinations for which the observations represent (approximate) Nash equilibria compared with optimal solutions enumerated in the subproblem. This row-generation approach extends prior methods for inverse integer optimization to competitive settings with (approximate) equilibria. We compare the decision-making of new entrants selecting locations based on scenarios, or information about the underlying distribution of customer attraction parameters (expected values), with new entrants using inversely estimated parameters for their location decisions. New entrants who rely on inversely optimized parameters can improve their profits. On average over a large set of synthetic numerical experiments, we observe improvements of 4–11%. This benefit can be realized with as little as one or two observations, yet additional observations help to increase prediction reliability significantly.

Abstracts:Hubs are critical components of transportation and distribution systems, and hub networks play a special role in freight and passenger transportation services worldwide. This paper studies a capacitated single allocation hub location problem with Bernoulli demands. Since the origin-destination (OD) demands are stochastic in nature, and the nodes are allocated to hubs before knowing their realized values, the actual total demand allocated to each hub is uncertain. Therefore, demand can exceed the capacity of hubs, rendering a need for outsourcing. The problem is studied under two distinct outsourcing policies, namely the facility and customer outsourcing. Mathematical models are developed for each case as two-stage stochastic programs. Deterministic equivalent formulations are obtained for problems, assuming a homogeneous demand distribution for all OD pairs. A Tabu Search-based algorithm is presented as a solution approach to deal with large problem instances. Extensive computational tests demonstrate the outstanding performance of the developed models and the metaheuristic procedure in terms of solution quality and computational time. The relevance of using stochastic programming approach for the problems is demonstrated via computational results. This study also reports solutions for problems with 200 nodes for the first time.