Approximation algorithms for single machine scheduling with one unavailability period

In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.      

A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”

In a recent paper, Chen [J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90–102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan  . Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP$P=\mathit{NP}$, which implies that Chen’s heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem.     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times

The paper deals with the m-machine permutation flow shop scheduling problem in which job processing times, along with a processing order, are decision variables. It is assumed that the cost of processing a job on each machine is a linear function of its processing time and the overall schedule cost to be minimized is the total processing cost plus maximum completion time cost. A algorithm for the problem with m = 2 is provided; the best approximation algorithm until now has a worst-case performance ratio equal to . An extension to the m-machine (m ≥2) permutation flow shop problem yields an approximation algorithm with a worst-case bound equal to

Full-size image

, where is the worst-case performance ratio of a procedure used, in the proposed algorithm, for solving the (pure) sequencing problem. Moreover, examples which achieve this bound for = 1 are also presented.     

A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness

This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods.     

A generalization of sensitivity of the inventory model with partial backorders

In this paper, we use the elementary techniques of differential calculus to investigate the sensitivity analysis of Montgomery et al.’s [Montgomery, D.C., Bazaraa, M.S., Keswani, A.K., 1973. Inventory models with a mixture of backorders and lost sales. Naval Research Logistics Quarterly 20, 225–263] inventory model with a mixture of backorders and lost sales and generalize Chu and Chung’s [Chu, P., Chung, K.J., 2004. The sensitivity of the inventory model with partial backorders. European Journal of Operational Research 152, 289–295] sensitivity analysis. We provide three numerical examples to demonstrate our findings, and remark the interpretation of the global minimum of the average annual cost at which the complete backordering occurs.     

Busy period analysis for the GI/M/1 queue with exponential vacations

We consider the busy period in the GI/M/1 queue with multiple exponential vacations. We derive the transform of the joint distribution of the length of a busy period, the number of customers served during the busy period, and the residual interarrival time at the instant the busy period ends.     

Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags

This paper shows that the single machine scheduling problem with multiple operations per job separated by minimum specified time-lags is NP-hard in the strong sense. Seven simple and polynomially bounded heuristic algorithms are developed for its solution when each job requires only two operations. Empirical evaluation shows that the percentage deviation of the heuristic solutions from their lower bounds is quite low and the effectiveness of these heuristic algorithms in finding optimal schedules increases with an increase in the number of jobs.     

Sensitivity analysis for the matching problem and its use in solving matching problems with a single side constraint

This paper develops certain sensitivity analysis capabilities for use with a primaldual matching code. The specific problem addressed is reoptimizing after the costs of a subset of the edges have been increased by a constant amount. This capability is applied to a dual ascent procedure for a Lagrangian relaxation of a matching problem with a single generalized upper bound side constraint. Some of the sensitivity analysis capabilities should be useful in other contexts as well. In particular, we give a method for solving for a set of dual variables that satisfy the strong complementary conditions given a blossom structure.Part of this work was performed while this author was visiting the University of Waterloo.     

Poisson比为1/2材料中球形空穴突变和球形空穴萌生的分岔问题研究

研究Ｐｏｉｓｓｏｎ比为１／２的Ｈｏｏｋｅ材料中,空穴的突变和萌生现象·求解一个球对称几何非线性弹性力学的移动边界（ｍｏｖｉｎｇｂｏｕｎｄａｒｙ）问题,空穴为球形,远离空穴处为三向均匀拉伸应力状态,在当前构形上列控制方程;在当前构形边界上列边界条件·找到了这个自由边界问题的封闭解并得到空穴半径趋于零时的叉型分岔解·计算结果显示,在位移＿载荷曲线上存在一个切分岔型分岔点（或鞍结点型分岔点、极值型分岔点）,这个分岔点说明在外力作用下空穴会发生突变,即突然“长大”;当球腔半径趋于零时,这个切分岔转化为叉型分岔（或分枝型分岔）,这个叉型分岔可以解释实心球中的空穴萌生现象     

On the Posets ( \user1Wk2 , < ){\left( {{\user1{\mathcal{W}}}^{k}_{2} , < } \right)} and their Connections with Some Homogeneous Inequalities of Degree 2

A class of ranked posets {(D _h ^k , ≪)} has been recently defined in order to analyse, from a combinatorial viewpoint, particular systems of real homogeneous inequalities between monomials. In the present paper we focus on the posets D ₂ ^k , which are related to systems of the form {x _a x _b * _abcd x _c x _d : 0 ≤ a, b, c, d ≤ k, * _abcd ∈ {<, >}, 0 < x ₀ < x ₁ < ...< x _k}. As a consequence of the general theory, the logical dependency among inequalities is adequately captured by the so-defined posets . These structures, whose elements are all the D ₂ ^k 's incomparable pairs, are thoroughly surveyed in the following pages. In particular, their order ideals – crucially significant in connection with logical consequence – are characterised in a rather simple way. In the second part of the paper, a class of antichains is shown to enjoy some arithmetical properties which make it an efficient tool for detecting incompatible systems, as well as for posing some compatibility questions in a purely combinatorial fashion.