This paper treats the Piggyback Transportation Problem: A large vehicle moves successive batches of small vehicles from a depot to a single launching point. Here, the small vehicles depart toward assigned customers, supply shipments, and return to the depot. Once the large vehicle has returned and another batch of small vehicles has been loaded at the depot, the process repeats until all customers are serviced. With autonomous driving on the verge of practical application, this general setting occurs whenever small autonomous delivery vehicles with limited operating range, e.g., unmanned aerial vehicles (drones) or delivery robots, need to be brought in the proximity of the customers by a larger vehicle, e.g., a truck. We aim at the most elementary decision problem in this context, which is inspired by Amazon’s novel last-mile concept, the flying warehouse. According to this concept, drones are launched from a flying warehouse and – after their return to an earthbound depot – are resupplied to the flying warehouse by an air shuttle. We formulate the Piggyback Transportation Problem, investigate its computational complexity, and derive suited solution procedures. From a theoretical perspective, we prove different important structural problem properties. From a practical point of view, we explore the impact of the two main cost drivers, the capacity of the large vehicle and the fleet size of small vehicles, on service quality.

Constraint programming solvers are known to perform remarkably well for most scheduling problems. However, when comparing the performance of different available solvers, there is usually no clear winner over all relevant problem instances. This gives rise to the question of how to select a promising solver when knowing the concrete instance to be solved. In this article, we aim to provide first insights into this question for the flexible job shop scheduling problem. We investigate relative performance differences among five constraint programming solvers on problem instances taken from the literature as well as randomly generated problem instances. These solvers include commercial and non-commercial software and represent the state-of-the-art as identified in the relevant literature. We find that two solvers, the IBM ILOG CPLEX CP Optimizer and Google’s OR-Tools, outperform alternative solvers. These two solvers show complementary strengths regarding their ability to determine provably optimal solutions within practically reasonable time limits and their ability to quickly determine high quality feasible solutions across different test instances. Hence, we leverage the resulting performance complementarity by proposing algorithm selection approaches that predict the best solver for a given problem instance based on instance features or parameters. The approaches are based on two machine learning techniques, decision trees and deep neural networks, in various variants. In a computational study, we analyze the performance of the resulting algorithm selection models and show that our approaches outperform the use of a single solver and should thus be considered as a relevant tool by decision makers in practice.

The scale of freight forwarding to the hinterland becomes an issue from the perspective of both – transport policy and cost efficiency of service providers. This problem is sharply visible in areas where ports, depots, inland intermodal terminals, exporters and importers are located, and full and empty containers satisfying demand and supply are frequently distributed creating a lot of traffic. Therefore solutions meeting the challenges of sustainable transport, responding to climate change and regulation of CO2 emissions are in need. In this paper, a variant of a Mixed Fleet Heterogeneous Dial-a-Ride Problem is proposed for optimal routing of trucks carrying full and empty 20-foot and 40-foot containers, with multiple pick-ups and deliveries. Transportation is performed by alternatively fueled vehicles (AFVs) for environmental reasons which causes a constraint of a limited driving range and a need of refueling. The main objective is minimising the total distance subject to matching the empty container demand and supply, necessary refueling of the trucks, and service time windows.

The intensity of local truck container transport results from the ubiquitous development of container shipping. Optimal routing of container trucks contributes to cost savings of the service provider but also the reduction of traffic and detrimental emissions. In this paper, a variant of a Mixed Fleet Heterogeneous Dial-a-Ride Problem is proposed for a container truck routing problem. Our aim is an optimal routing of trucks carrying full and empty 20-foot and 40-foot containers, with multiple pick-ups and deliveries. Transportation is performed by alternatively fuelled vehicles (AFVs) for environmental reasons. The AFVs have a limited driving range and are allowed to refuel in any alternative fuel station. The main objective is minimising the total distance subject to matching the empty container demand and supply, necessary refuelling of the trucks, and service time windows.

Braverman et al. [Math. Oper. Res. 41(1), (2016), pp. 352–376], introduce the problem Provision-after-Wait which is to find a stable (ey free) assignment of n patients to m hospitals, and their waiting times before admission, such that the social welfare is maximized, subject to a limited budget. Chan et al. [ACM Trans. Econ. Comput. 5(2), (2017), Article 12, pp. 12:1–12:36] focus on a natural case of d-ordered preferences, in which patients are ordered according to the differences of their values between consecutive hospitals. For this case, they provide a sophisticated proof of ordinary NP-hardness, reduce it to the problem called Ordered Knapsack, and develop a fully polynomial time approximation scheme for Ordered Knapsack. We present a simple proof that Ordered Knapsack is NP-hard, which implies NP-hardness of a more restrictive case of the original problem, and present an alternative fully polynomial time approximation scheme with a reduced run time by a quadratic factor of n, for a fixed m. A similar algorithm is developed to find a solution for which the social welfare is as high as for the optimal solution of Ordered Knapsack, and the budget limit can be exceeded by at most 1-ε times. We also present polynomial algorithms for the cases of Ordered Knapsack, in which the number of distinct input parameters is fixed.

The mixed fleet heterogeneous dial-a-ride problem (MF-HDARP) consists of designing vehicle routes for a set of users by using a mixed fleet including both heterogeneous coentional and alternative fuel vehicles. In addition, a vehicle is allowed to refuel from a fuel station to eliminate the risk of running out of fuel during its service. We propose an efficient hybrid adaptive large neighborhood search (hybrid ALNS) algorithm for the MF-HDARP. The computational experiments show that the algorithm produces high quality solutions on our generated instances and on HDARP benchmarks instances. Computational experiments also highlight that the newest components added to the standard ALNS algorithm enhance intensification and diversification during the search process.

One of the most known results in the machine scheduling is Lawler’s algorithm to minimize the maximum cost of jobs processed by a single machine subject to precedence constraints. We consider an uncertain version of the same min-max cost scheduling problem. The cost function of each job depends on the job completion time and on an additional generalized numerical parameter, which may be a tuple of parameters. For each job, both, its processing time and the additional parameter are uncertain, only intervals of possible values of these parameters are known. We analyse certain classes of cost functions and develop polynomial algorithms which construct min-max regret solutions. The considered problems cover the most general range of studied cases of interval uncertainty. In the only two papers that present algorithms for minimizing the maximum regret for the problem with uncertain job processing times, the algorithms are based on extremal scenarios, where some uncertain parameters take their maximum values, while all others take their minimum possible values. We show that it is impossible to always limit the search to extremal scenarios. Our approach is based on new ideas different from those underlying previous work. Finally, we show that our approach outperforms all known results for constructing min-max regret solutions for the min-max cost scheduling problem under uncertainty of job processing times.

This handbook provides a comprehensive introduction to the theory and applications of scheduling in advanced planning and computer systems. It addresses a broad audience including practitioners and researchers interested in scheduling, as well as graduate and advanced undergraduate students in the fields of computer science and computer engineering, operations research, industrial and real-time engineering, management science, business administration and information systems, and applied mathematics. The book begins by providing an introduction to and basic concepts from discrete mathematics. Single and multiple processor systems are covered, with a focus on multiprocessor tasks and hard real-time systems. Flow shop and open shop scheduling, as well as scheduling in job shops, are explained in detail. Issues like limited processor availability, time-dependence, resource constraints and imprecise computations are dealt with in dedicated chapters. Special attention is given to online scheduling, constraint programming and disjunctive scheduling. The book also features applications and cases iolving flexible manufacturing systems, computer integrated production scheduling and logistics. In particular it presents case studies on optimization procedures for the production of acrylic glass and of helicopter parts in a flexible manufacturing system, an efficient decision support system for airport gate scheduling, concrete delivery planning, and berth and quay crane allocation at seaports. This handbook provides a comprehensive introduction to the theory and applications of scheduling in advanced planning and computer systems. It addresses a broad audience including practitioners and researchers interested in scheduling, as well as graduate and advanced undergraduate students in the fields of computer science and computer engineering, operations research, industrial and real-time engineering, management science, business administration and information systems, and applied mathematics. The book begins by providing an introduction to and basic concepts from discrete mathematics. Single and multiple processor systems are covered, with a focus on multiprocessor tasks and hard real-time systems. Flow shop and open shop scheduling, as well as scheduling in job shops, are explained in detail. Issues like limited processor availability, time-dependence, resource constraints and imprecise computations are dealt with in dedicated chapters. Special attention is given to online scheduling, constraint programming and disjunctive scheduling. The book also features applications and cases involving flexible manufacturing systems, computer integrated production scheduling and logistics. In particular it presents case studies on optimization procedures for the production of acrylic glass and of helicopter parts in a flexible manufacturing system, an efficient decision support system for airport gate scheduling, concrete delivery planning, and berth and quay crane allocation at seaports. // This handbook provides a comprehensive introduction to the theory and applications of scheduling in advanced planning and computer systems. It addresses a broad audience including practitioners and researchers interested in scheduling, as well as graduate and advanced undergraduate students in the fields of computer science and computer engineering, operations research, industrial and real-time engineering, management science, business administration and information systems, and applied mathematics. The book begins by providing an introduction to and basic concepts from discrete mathematics. Single and multiple processor systems are covered, with a focus on multiprocessor tasks and hard real-time systems. Flow shop and open shop scheduling, as well as scheduling in job shops, are explained in detail. Issues like limited processor availability, time-dependence, resource constraints and imprecise computations are dealt with in dedicated chapters. Special attention is given to online scheduling, constraint programming and disjunctive scheduling. The book also features applications and cases involving flexible manufacturing systems, computer integrated production scheduling and logistics. In particular it presents case studies on optimization procedures for the production of acrylic glass and of helicopter parts in a flexible manufacturing system, an efficient decision support system for airport gate scheduling, concrete delivery planning, and berth and quay crane allocation at seaports.

This article revisits the scheduling problem in a two-machine flow-shop system with the total late work criterion, which penalizes parts of jobs executed after their due dates. Firstly, it is shown that a lower bound presented previously in the literature, in the context of a branch-and-bound algorithm proposed for the same problem, is ialid. Then a novel proposal of the branch-and-bound method is given equipped with a new lower-bound technique, as well as an upper-bound and dominance rules. Numerical experiments show that the newly proposed lower-bound technique works well in cutting unpromising branches.

We address an optimization problem that arises at seaports where containers are transported between stacking areas and small buffer areas of restricted capacity that are located within the reach of quay cranes. The containers are transported by straddle carriers that have to be routed such that given unloading and loading sequences of the containers at the quay cranes are respected. The objective is to minimize the turnaround times of the vessels. We analyze the problem’s computational complexity, present an integer program, and propose a heuristic framework that is based on decomposing the problem into its routing component and a component that handles the time variables and buffer capacities. The framework is analyzed in computational tests that are based on real-world data. Based on these tests, we analyze the question of whether or not it pays off to deviate from the approach of permanently assigning a fixed number of straddle carriers to each quay crane, which is the strategy that is currently implemented at the port.