Scheduling
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.
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.
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.
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.
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.
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.
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.
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.
