Coordinating multi-location production and customer delivery

We study two parallel machine scheduling problems with equal processing time jobs and delivery times and costs. The jobs are processed on machines which are located at different sites, and delivered to a customer by a single vehicle. The first objective considered is minimizing the sum of total weighted completion time and total vehicle delivery costs. The second objective considered is minimizing the sum of total tardiness and total vehicle delivery costs. We develop several interesting properties of an optimal scheduling and delivery policy, and show that both problems can be solved by reduction to the Shortest-Path problem in a corresponding network. The overall computational effort of both algorithms is O(n ^m2+m+1) (where n and m are the number of jobs and the number of machines, respectively) by the application of the Directed Acyclic Graph (DAG) method. We also discuss several special cases for which the overall computational effort can be significantly reduced.     

Integrated location and two-echelon inventory network design under uncertainty

In this paper, we propose a two-stage stochastic model to address the design of an integrated location and two-echelon inventory network under uncertainty. The central issue in this problem is to design and operate an effective and efficient multi-echelon supply chain distribution network and to minimize the expected system-wide cost of warehouse location, the allocation of warehouses to retailers, transportation, and two-echelon inventory over an infinite planning horizon. We structure this problem as a two-stage nonlinear discrete optimization problem. The first stage decides the warehouses to open and the second decides the warehouse-retailer assignments and two-echelon inventory replenishment strategies. Our modeling strategy incorporates various probable scenarios in the integrated multi-echelon supply chain distribution network design to identify solutions that minimize the first stage costs plus the expected second stage costs. The two-echelon inventory cost considerations result in a nonlinear objective which we linearize with an exponential number of variables. We solve the problem using column generation. Our computational study indicates that our approach can solve practical problems of moderate-size with up to twenty warehouse candidate locations, eighty retailers, and ten scenarios efficiently.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Dynamic decision making for graphical models applied to oil exploration

We present a framework for sequential decision making in problems described by graphical models. The setting is given by dependent discrete random variables with associated costs or revenues. In our examples, the dependent variables are the potential outcomes (oil, gas or dry) when drilling a petroleum well. The goal is to develop an optimal selection strategy of wells that incorporates a chosen utility function within an approximated dynamic programming scheme. We propose and compare different approximations, from naive and myopic heuristics to more complex look-ahead schemes, and we discuss their computational properties. We apply these strategies to oil exploration over multiple prospects modeled by a directed acyclic graph, and to a reservoir drilling decision problem modeled by a Markov random field. The results show that the suggested strategies clearly improve the naive or myopic constructions used in petroleum industry today. This is useful for decision makers planning petroleum exploration policies.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries

We study a supply chain scheduling problem, where a common due date is assigned to all jobs and the number of jobs in delivery batches is constrained by the batch size. Our goal is to minimize the sum of the weighted number of tardy jobs, the due-date-assignment costs and the batch-delivery costs. We show that some well-known NP\mathcal{NP}-hard problems reduce to our problem. Then we propose a pseudo-polynomial algorithm for the problem, establishing that it is NP\mathcal{NP}-hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.     

Reputation-based winner determination problem for combinatorial transportation procurement auctions

This paper proposes a reputation-based winner determination problem for transportation procurement auctions where the allocation of long-term contracts to carriers is decided with respect to both bid ask-prices and carriers reputation. The objective is to manage the trade-off between transport costs and the quality of service during operations. Carriers reputation is translated into unexpected hidden cost that represents the possible additional cost that the shipper may incur when dealing with a set of winning carriers. This cost depends essentially on the carriers reputation as evaluated by the shipper running the auction. To evaluate carriers reputations, the shipper uses a number of service attributes with different weights depending on shipping contracts.     

Economic and environmental comparison of grouping strategies in coordinated multi-item inventory systems

The increasing concerns for sustainability throughout supply chains are enforcing managers to plan their operations considering not only economic but also environmental performance. Inventory management is one of the main determinants of the costs incurred and emissions generated throughout supply chains as it defines the level of logistical operations, freight transportation, and warehousing activities. In this study, we analyze a multi-item inventory control system with coordinated shipments. In particular, we revisit the well-known deterministic joint replenishment problem (JRP) with economic and environmental objectives under indirect and direct grouping strategies. We formulate and develop solution methods for each bi-objective JRP and compare direct and indirect grouping strategies with respect to their economic as well as environmental performance. A set of numerical studies is presented to examine the settings where a specific grouping strategy can be economically and environmentally better than the other.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

A coordinated location-inventory model

We consider a coordinated location-inventory model where distribution centers (DCs) follow a periodic-review (R, S) inventory policy and system coordination is achieved by choosing review intervals at the DCs from a menu of permissible choices. We introduce two types of coordination: partial coordination where each DC may choose its own review interval from the menu, and full coordination where all the DCs have an identical review interval. While full coordination increases the location and inventory costs, it likely reduces the overall costs of running the system (when the operational costs such as delivery scheduling are taken into account). The problem is to determine the location of the DCs to be opened, the assignment of retailers to DCs, and the inventory policy parameters at the DCs such that the total system-wide cost is minimized. The model is formulated as a nonlinear integer-programming problem and a Lagrangian relaxation algorithm is proposed to solve it. Computational results show that the proposed algorithm is very efficient. The results of our computational experiments and case study suggest that the location and inventory cost increase due to full coordination, when compared to partial coordination, is not significant. Thus, full coordination, while enhancing the practicality of the model, is economically justifiable.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

Quantifying the value of buyer–vendor coordination: Analytical and numerical results under different replenishment cost structures

Despite a growing interest in channel coordination, no detailed analytical or numerical results measuring its impact on system performance have been reported in the literature. Hence, this paper aims to develop analytical and numerical results documenting the system-wide cost improvement rates that are due to coordination. To this end, we revisit the classical buyer–vendor coordination problem introduced by Goyal [S.K. Goyal, An integrated inventory model for a single-supplier single-customer problem. International Journal of Production Research 15 (1976) 107–111] and extended by Toptal et al. [A. Toptal, S. Çetinkaya, C.-Y. Lee, The buyer–vendor coordination problem: modeling inbound and outbound cargo capacity and costs, IIE Transactions on Logistics and Scheduling 35 (2003) 987–1002] to consider generalized replenishment costs under centralized decision making. We analyze (i) how the counterpart centralized and decentralized solutions differ from each other, (ii) under what circumstances their implications are similar, and (iii) the effect of generalized replenishment costs on the system-wide cost improvement rates that are due to coordination. First, considering Goyal’s basic setting, we show that the improvement rate depends on cost parameters. We characterize this dependency analytically, develop analytical bounds on the improvement rate, and identify the problem instances in which considerable savings can be achieved through coordination. Next, we analyze Toptal et al.’s [A. Toptal, S. Çetinkaya, C.-Y. Lee, The buyer–vendor coordination problem: modeling inbound and outbound cargo capacity and costs, IIE Transactions on Logistics and Scheduling 35 (2003) 987–1002] extended setting that considers generalized replenishment costs representing inbound and outbound transportation considerations, and we present detailed numerical results quantifying the value of coordination. We report significant improvement rates with and without explicit transportation considerations, and we present numerical evidence which suggests that larger rates are more likely in the former case.     

Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems

We consider the real-time scheduling of full truckload transportation orders with time windows that arrive during schedule execution. Because a fast scheduling method is required, look-ahead heuristics are traditionally used to solve these kinds of problems. As an alternative, we introduce an agent-based approach where intelligent vehicle agents schedule their own routes. They interact with job agents, who strive for minimum transportation costs, using a Vickrey auction for each incoming order. This approach offers several advantages: it is fast, requires relatively little information and facilitates easy schedule adjustments in reaction to information updates. We compare the agent-based approach to more traditional hierarchical heuristics in an extensive simulation experiment. We find that a properly designed multi-agent approach performs as good as or even better than traditional methods. Particularly, the multi-agent approach yields less empty miles and a more stable service level.     

On-line supply chain scheduling problems with preemption

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal.     

Formulation and a two-phase matheuristic for the roaming salesman problem: Application to election logistics

In this paper we investigate a novel logistical problem. The goal is to determine daily tours for a traveling salesperson who collects rewards from activities in cities during a fixed campaign period. We refer to this problem as the Roaming Salesman Problem (RSP) motivated by real-world applications including election logistics, touristic trip planning and marketing campaigns. RSP can be characterized as a combination of the traditional Periodic TSP and the Prize-Collecting TSP with static arc costs and time-dependent node rewards. Commercial solvers are capable of solving small-size instances of the RSP to near optimality in a reasonable time. To tackle large-size instances we propose a two-phase matheuristic where the first phase deals with city selection while the second phase focuses on route generation. The latter capitalizes on an integer program to construct an optimal route among selected cities on a given day. The proposed matheuristic decomposes the RSP into as many subproblems as the number of campaign days. Computational results show that our approach provides near-optimal solutions in significantly shorter times compared to commercial solvers.     

Two-agent scheduling to minimize the total cost

Two agents, each having his own set of jobs, compete to perform their own jobs on a common processing resource. Each job of the agents has a weight that specifies its importance. The cost of the first agent is the maximum weighted completion time of his jobs while the cost of the second agent is the total weighted completion time of his jobs. We consider the scheduling problem of determining the sequence of the jobs such that the total cost of the two agents is minimized. We provide a 2-approximation algorithm for the problem, show that the case where the number of jobs of the first agent is fixed is NP-hard, and devise a polynomial time approximation scheme for this case.     

Minimizing earliness and tardiness penalties in a single-machine problem with a common due date

Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this paper we examine the single-machine scheduling problem with a common due date. Performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we propose a tabu search-based heuristic and a genetic algorithm which exploit specific properties of the optimal solution. Hybrid strategies are also analyzed to improve the performance of these methods. The proposed approaches are examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains

In this paper, an integrated due date assignment and production and batch delivery scheduling problem for make-to-order production system and multiple customers is addressed. Consider a supply chain scheduling problem in which n orders (jobs) have to be scheduled on a single machine and delivered to K customers or to other machines for further processing in batches. A common due date is assigned to all the jobs of each customer and the number of jobs in delivery batches is constrained by the batch size. The objective is to minimize the sum of the total weighted number of tardy jobs, the total due date assignment costs and the total batch delivery costs. The problem is NP-hard. We formulate the problem as an Integer Programming (IP) model. Also, in this paper, a Heuristic Algorithm (HA) and a Branch and Bound (B&B) method for solving this problem are presented. Computational tests are used to demonstrate the efficiency of the developed methods.     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.     

A rank-based approach to the sequential selection and assignment problem

In the classical sequential assignment problem, “machines” are to be allocated sequentially to “jobs” so as to maximize the expected total return, where the return from an allocation of job j to machine k is the product of the value x_j of the job and the weight p_k of the machine. The set of m machines and their weights are given ahead of time, but n jobs arrive in sequential order and their values are usually treated as independent, identically distributed random variables from a known univariate probability distribution with known parameter values. In the paper, we consider a rank-based version of the sequential selection and assignment problem that minimizes the sum of weighted ranks of jobs and machines. The so-called “secretary problem” is shown to be a special case of our sequential assignment problem (i.e., m = 1). Due to its distribution-free property, our rank-based assignment strategy can be successfully applied to various managerial decision problems such as machine scheduling, job interview, kidney allocations for transplant, and emergency evacuation plan of patients in a mass-casualty situation.     

A greedy look-ahead heuristic for the vehicle routing problem with time windows

In this paper we consider the problem of physically distributing finished goods from a central facility to geographically dispersed customers, which pose daily demands for items produced in the facility and act as sales points for consumers. The management of the facility is responsible for satisfying all demand, and promises deliveries to the customers within fixed time intervals that represent the earliest and latest times during the day that a delivery can take place. We formulate a comprehensive mathematical model to capture all aspects of the problem, and incorporate in the model all critical practical concerns such as vehicle capacity, delivery time intervals and all relevant costs. The model, which is a case of the vehicle routing problem with time windows, is solved using a new heuristic technique. Our solution method, which is based upon Atkinson's greedy look-ahead heuristic, enhances traditional vehicle routing approaches, and provides surprisingly good performance results with respect to a set of standard test problems from the literature. The approach is used to determine the vehicle fleet size and the daily route of each vehicle in an industrial example from the food industry. This actual problem, with approximately two thousand customers, is presented and solved by our heuristic, using an interface to a Geographical Information System to determine inter-customer and depot–customer distances. The results indicate that the method is well suited for determining the required number of vehicles and the delivery schedules on a daily basis, in real life applications.