Scheduling
In this paper, we aim to study the structure choice of supply chains under competitive environment with uncertain demand. We consider two competing supply chains, each of which chooses to either vertically integrate or decentralize with coordinating contracts.We first analyze firms’ strategic behavior under given supply chain structures: two integrated chains (II), two decentralized chains (DD), and a mixed structure with one decentralized chain and one integrated chain. We then compare different supply chain structures and examine the equilibrium structure choice. We find that the equilibrium structure depends on the product characteristics. For substitutable products, DD is the equilibrium supply chain structure choice, whereas for complementary products, II is the equilibrium structure. Furthermore, a high demand uncertainty strengthens these equilibrium choices.
In this paper, we examine some principles in managing manufacturing systems. These principles are concerned with the variability, the utilization, the rework, the lead time, and the constant work-in-process efficiency. While these principles are developed through analyzing some simpler disconnected flow line manufacturing systems, we examine whether they can have broad applications. For some of these principles, we provide sufficient conditions, while for others, we provide counterexamples. Our analysis suggests that we should be very cautious about these laws when applied to non-Markov and non-tandem systems.
For reducing traffic jams without widening streets, we come up with a tenement rearrangement problem. In this paper, we study a tenement allocation model which includes two types of tenants, i.e., typical tenants and special tenants who owned houses by themselves. The optimal allocation is that total transportation cost is minimized without undermining tenants’ individual housing preference or increasing individual cost. Besides, we present a Modified Hungarian Algorithm for the above tenement allocation problem and prove that it can be solved in polynomial time. Furthermore, computational tests show that this algorithm has a good performance.
In airline revenue management, after differentiating products on each itinerary according to various restrictions, management needs to set the prices for the products. A deterministic joint pricing and seat allocation model is proposed. It is reduced to a separable concave programming problem and thus readily solvable. Focusing on a special hub-to-hub airline network, monotonicity of the pricing decisions is explored. Using a nonlinear primal–dual technique, it is shown that some itineraries’ optimal prices are decreasing, while some other itineraries’ optimal prices are increasing with a capacity change in either a side leg or the middle leg. Such structural properties add important managerial insights into the pricing model for revenue managers in an airline company.
In this paper, we investigate the obnoxious facility location game with weighted agents. First, we design a randomized group strategy-proof mechanism with approximation ratio 3Wmax/2Wmin when the weighted agents are located on a line; then, on the cycle metric, we also discuss the strategy-proofness and the approximation ratios of a class of group strategy-proof deterministic mechanisms.
We consider the online scheduling problem on two parallel machines with the Grade of Service (GoS) eligibility constraints. The jobs arrive over time, and the objective is to minimize the makespan. We develop a (1 + α)-competitive optimal algorithm, where α ≈ 0.555 is a solution of α3 − 2α2 − α + 1 = 0.
We study the computational complexities of three problems on multi-agent scheduling on a single machine. Among the three problems, the computational complexities of the first two problems were still open and the last problem was shown to be unary NP-hard in the literature. We show in this paper that the first two problems are unary NP-hard. We also show that the unary NP-hardness proof for the last problem in the literature is invalid, and so, the exact complexity of the problem is still open.
This paper deals with a scheduling problem with parallel-batching machines from a game theoretic perspective. There are m parallel-batching machines, each of which can handle up to b jobs simultaneously as a batch. The processing time of a batch is the time required for processing the longest job in the batch, and all the jobs in a batch start and complete at the same time. There are n jobs. Each job is owned by a rational and selfish agent. The agent of a job chooses a machine for processing its own job. The aim of each agent is to minimize the completion time of its job while the system tries tominimize the maximal completion time over all jobs, the makespan.We design a coordination mechanism for the scheduling game problem. We discuss the existence of Nash equilibria of the mechanism and showthat it has a price of anarchy 2.
Two-agent single-machine scheduling problem is considered in this paper. Agent A’s goal is to minimize the sum of the total weighted delivery time and the total delivery cost, and agent B has the delivery time window. First, the NP-hardness of the general problem is proved, and then two special cases are considered. One case is that A’s jobs have agreeable ratio and this problem is still NP-hard. A pseudo-polynomial dynamic programming algorithm and a 3 2 -approximation algorithm are designed. In the other case, A’s jobs have agreeable ratio and B’s jobs have deadline at the same time. This problem is polynomial solvable.
As an effective travel demand management means, park-and-ride (P&R) mode is an important part of urban traffic. In a traffic corridor with P&R service, suppose that the travel time on highway is uncertain, a cumulative prospect theory (CPT)-based travel decision-making model is established with two travel modes of driving all the way and (P&R). With this setting, the effect of various factors such as the transit fare rate, the parking fee and the total travel demand on the CPT-based and expected utility theory (EUT)-based equilibrium results are compared. In addition, the sensitivity analysis focus on CPT-related parameters are also performed. The numerical results in our case show that the equilibrium flow on P&R mode is always underestimated in an EUT-based model, especially for a low total travel demand. Also, it is found that reducing the transit fare rate or parking fee for P&R station and raising the parking fee for CBD has the same effect on promoting more commuters transfer to P&R mode, whatever CPT-based or EUT-based model is employed.Furthermore, commuter’s reference dependence characteristic is also observed in a CPT-based model, and it is especially noticeable when the road uncertainty is large.
This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is assigned to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In this paper, we propose a new linear programming (LP) relaxation for this problem by incorporating a set of validity constraints into the classical formulations by Ernst and Krishnamoorthy (Locat Sci 4:139–154, Ann Op Res 86:141–159). A geometric rounding algorithm is then used to obtain an integral solution from the fractional solution. We show that by incorporating the validity constraints, the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort and the solution obtained often has a much smaller gap with the optimal solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little costs.
Scheduling with group technology has been a vivid research area in the past decades. However, group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios. Accordingly, this paper considers group scheduling problems with a kind of general group variable processing times model, where the actual processing time of each job in group is variable due to the dual effect of both the job position and the group position. The objectives of two types of considered problems are to minimize the makespan and the total completion time, respectively. Based on the decomposition analysis, the mathematical logic analysis and the computational complexity proof, it is obtained that the makespan minimization problem and the total completion time minimization problem are both polynomially solvable under the condition that the group number is constant. For three special cases of considered problems, polynomial solving algorithms with lower computational complexity are proposed.
We study single-machine scheduling problems with a single maintenance activity (MA) of length p0 under three types of assumptions: (A) the MA is required in a fixed time interval [T−p0,T ] with T⩾p0 and the job processing is of preemptive and resumable; (B) the MA is required in a relaxed time interval [0, T] withT⩾p0 and the job processing is of nonpreemptive; (C) the MA is required in a relaxed time interval [T0,T]with 0⩽T0⩽T−p0 and the job processing is of nonpreemptive. We show in this paper that, up to the time complexity for solving scheduling problems, assumptions (A) and (B) are equivalent, and moreover, if T−(T0+p0) is greater than or equal to the maximum processing time of all jobs, the assumption (C) is also equivalent to (A) and (B). As an application, we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions, respectively, and present corresponding time-complexity results.
We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time. In this problem, jobs arrive over time and the processing times (of the jobs) are identical, and the batch capacity is bounded. For this problem, we provide a best possible online algorithm with a competitive ratio of (5–√+1)/2. Moreover, when restricted to dense-algorithms, we present a best possible dense-algorithm with a competitive ratio of 2.
Data envelopment analysis has been successfully used in resource allocation problems. However, to the best of our knowledge, there are no allocation models proposed in the literature that simultaneously take both the global efficiency and growing potential into account. Hence, this research aims at developing an allocation model for extra input resources, which maximizes the global technical efficiency and scale efficiency of a decision-making unit (DMU) set while maintaining the pure technical efficiency (i.e., growing potential) of each DMU. To this purpose, we first discuss the optimal resources required by each DMU. We prove that the optimal inputs for the DMU are actually the inputs of some most productive scale size (MPSS). We then propose the allocation model based on the discussion on the case of one DMU. The allocation model is illustrated using two numerical examples.
Error Bounds for Generalized Mixed Vector Equilibrium Problems via a Minimax Strategy
In this paper, by using scalarization techniques and a minimax strategy, error bound results in terms of gap functions for a generalized mixed vector equilibrium problem are established, where the solutions for vector problems may be general sets under natural assumptions, but are not limited to singletons. The other essentially equivalent approach via a separation principle is analyzed. Special cases to the classical vector equilibrium problem and vector variational inequality are also discussed.
This paper considers competitive project scheduling on two unbounded parallel batch machines. There are two competing firms, and each firm has an unbounded parallel batch machine. All projects must be performed in batches by Firms 1 and 2 on their machines, respectively. The profit that each firm obtains from each project depends on whether the firm finishes the job before or after its competitor. In the first problem, given a feasible schedule for Firm 1, the objective is to find an optimal schedule to maximize the total reward for Firm 2 under the given schedule for Firm 1. The corresponding total reward for Firm 1 is called the worst-case total reward of the given schedule for Firm 1. In the second problem, the objective is to find an optimal schedule for Firm 1 to maximize the worst-case total reward. We provide optimal algorithms for the two problems, respectively.
