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