Critical acceptance values and sample sizes of a variables sampling plan for very low fraction of defectives

Acceptance sampling plans are practical tools for quality control applications, which involve quality contracting on product orders between the vendor and the buyer. Those sampling plans provide the vendor and the buyer rules for lot sentencing while meeting their preset requirements on product quality. In this paper, we introduce a variables sampling plan for unilateral processes based on the one-sided process capability indices _CPU$C_{\mathrm{PU}}$ (or _CPL)$C_{\mathrm{PL}})$, to deal with lot sentencing problem with very low fraction of defectives. The proposed new sampling plan is developed based on the exact sampling distribution rather than approximation. Practitioners can use the proposed sampling plan to determine accurate number of product items to be inspected and the corresponding critical acceptance value, to make reliable decisions. We also tabulate the required sample size n$n$ and the corresponding critical acceptance value _C0$C_0$ for various α$\alpha$-risks, β$\beta$-risks, and the levels of lot or process fraction of defectives that correspond to acceptable and rejecting quality levels.     

Optimization models for the tool change scheduling problem

Traditional machine scheduling literature generally assumes that a machine is available at all times. Yet this assumption may not be accurate in real manufacturing systems. In many cases, a machine's tool must be changed after it has continuously worked for a period of time. This paper deals with a single machine scheduling problem subject to tool wear, given the allowed maximum continuous working time of the machine is _TL$T_{\mathrm{L}}$ (tool life) and the tool change time is _TC$T_{\mathrm{C}}$. Job processing and tool changes are scheduled simultaneously. In this paper, we examine this problem to minimize the total tardiness of jobs. Two mixed binary integer programming models are developed to optimally solve this problem. Computational experiments are performed to evaluate the models’ efficiency.     

Efficient composite heuristics for total flowtime minimization in permutation flow shops

In this paper, permutation flow shops with total flowtime minimization are considered. General flowtime computing (GFC) is presented to accelerate flowtime computation. A newly generated schedule is divided into an unchanged subsequence and a changed part. GFC computes total flowtime of a schedule by inheriting temporal parameters from its parent in the unchanged part and computes only those of the changed part. Iterative methods and LR (developed by Liu J, Reeves, CR. Constructive and composite heuristic solutions to theP∥Σ_Ci$P\parallel \Sigma C_i$ scheduling problem, European Journal of Operational Research 2001; 132:439–52) are evaluated and compared as solution improvement phase and index development phase. Three composite heuristics are proposed in this paper by integrating forward pair-wise exchange-restart (FPE-R) and FPE with an effective iterative method. Computational results show that the proposed three outperform the best existing three composite heuristics in effectiveness and two of them are much faster than the existing ones.     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

Improving routing and scheduling decisions at a distributor of industrial gasses

This paper investigates cyclical inventory replenishment for a company's regional distribution center that supplies, distributes, and manages inventory of carbon dioxide (_CO2)$({\mathrm{CO}}_2)$ at over 900 separate customer sites in Indiana. The company previously experienced high labor costs with excessive overtime and maintained a regular back-log of customers experiencing stockouts. To address these issues we implemented a three-phase heuristic for the cyclical inventory routing problem encountered at one of the company's distribution centers. This heuristic determines regular routes for each of three available delivery vehicles over a 12-day delivery horizon while improving four primary performance measures: delivery labor cost, stockouts, delivery regularity, and driver–customer familiarity. It does so by first determining three sets of cities (one for each delivery vehicle) that must be delivered to each day based on customer requirements. Second, the heuristic assigns the remaining customers in other cities to one of the three “backbone routes” determined in phase 1. And third, it balances customer deliveries on each daily route over the schedule horizon. Through our methodology, we were able to significantly reduce overtime, driving time, and labor costs while improving customer service.     

Single-machine batch delivery scheduling with an assignable common due window

This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We show that the problem can be optimally solved in O(n⁸)$O(n^8)$ time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.     

Precision parameter in the variable precision rough sets model: an application

Despite their diverse applications in many domains, the variable precision rough sets (VPRS) model lacks a feasible method to determine a precision parameter (β)$(\beta )$ value to control the choice of β$\beta$-reducts. In this study we propose an effective method to find the β$\beta$-reducts. First, we calculate a precision parameter value to find the subsets of information system that are based on the least upper bound of the data misclassification error. Next, we measure the quality of classification and remove redundant attributes from each subset. We use a simple example to explain this method and even a real-world example is analyzed. Comparing the implementation results from the proposed method with the neural network approach, our proposed method demonstrates a better performance.     

Two-stage time minimizing assignment problem

This paper deals with the optimal selection of m out of n facilities to first perform m   given primary jobs in Stage-I followed by the remaining (n-m)$(n-m)$ facilities performing optimally the (n-m)$(n-m)$ secondary jobs in Stage-II. It is assumed that in both the stages facilities perform in parallel. The aim of the proposed study is to find that set of m   facilities performing the primary jobs in Stage-I for which the sum of the overall completion times of jobs in Stage-I and the corresponding optimal completion time of the secondary jobs in Stage-II by the remaining (n-m)$(n-m)$ facilities is the minimum. The developed solution methodology involves solving the standard time minimizing and cost minimizing assignment problems alternately after forbidding some facility-job pairings and suggests a polynomially bound algorithm. This proposed algorithm has been implemented and tested on a variety of test problems and its performance is found to be quite satisfactory.     

Probabilistic Modeling of Flood Hazard and its Risk Assessment for Eastern Region of India

This article models flood occurrence probabilistically and its risk assessment. It incorporates atmospheric parameters to forecast rainfall in an area. This measure of precipitation, together with river and ground parameters, serve as parameters in the model to predict runoff and subsequently inundation depth of an area. The inundation depth acts as a guide for predicting flood proneness and associated hazard. The vulnerability owing to flood has been analyzed as social vulnerability $(V_S)$, vulnerability to property $(V_P)$, and vulnerability to the location in terms of awareness $(V_A)$. The associated risk has been estimated for each area. The distribution of risk values can be used to classify every area into one of the six risk zones—namely, very low risk, low risk, moderately low risk, medium risk, high risk, and very high risk. The prioritization regarding preparedness, evacuation planning, or distribution of relief items should be guided by the range on the risk scale within which the area under study falls. The flood risk assessment model framework has been tested on a real‐life case study. The flood risk indices for each of the municipalities in the area under study have been calculated. The risk indices and hence the flood risk zone under which a municipality is expected to lie would alter every day. The appropriate authorities can then plan ahead in terms of preparedness to combat the impending flood situation in the most critical and vulnerable areas.     

Single cycle policies for the one-warehouse N-retailer inventory/distribution system

We address a multi-echelon inventory system with one-warehouse and N  -retailers. The demand at each retailer is assumed to be known and satisfied by the warehouse. Shortages are not allowed and lead times are negligible. Costs at each facility consist of a fixed charge per order and a holding cost. The goal is to determine single-cycle policies which minimize the average cost per unit time, that is, the sum of the average holding and setup costs per unit time at the retailers and at the warehouse. We propose a O(NlogN)$\mathrm{O}(N\log N)$ heuristic procedure to compute efficient single-cycle policies. This heuristic is compared with other approaches proposed by Schwarz, Graves and Schwarz and Muckstadt and Roundy. We carry out a computational study to test the effectiveness of the heuristic and to compare the performance of the different procedures. From the computational results, it is shown that the new heuristic provides, on average, better single-cycle policies than those given by the Muckstadt and Roundy method.     

Approximating <Emphasis Type="Italic">k</Emphasis>-generalized connectivity via collapsing HSTs

An instance of the k -generalized connectivity problem consists of an undirected graph G=(V,E), whose edges are associated with non-negative costs, and a collection \({\mathcal{D}}=\{(S_{1},T_{1}),\ldots,(S_{d},T_{d})\}\) of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ??G connects a demand (S _i ,T _i ) when it contains a path with one endpoint in S _i and the other in T _i . Given an integer parameter k, the goal is to identify a minimum cost subgraph that connects at least k demands in \({\mathcal{D}}\).Alon, Awerbuch, Azar, Buchbinder and Naor (SODA ’04) seem to have been the first to consider the generalized connectivity paradigm as a unified machinery for incorporating multiple-choice decisions into network formation settings. Their main contribution in this context was to devise a multiplicative-update online algorithm for computing log-competitive fractional solutions, and to propose provably-good rounding procedures for important special cases. Nevertheless, approximating the generalized connectivity problem in its unconfined form, where one makes no structural assumptions about the underlying graph and collection of demands, has remained an open question up until a recent O(log?² nlog?² d) approximation due to Chekuri, Even, Gupta and Segev (SODA ’08). Unfortunately, the latter result does not extend to connecting a pre-specified number of demands. Furthermore, even the simpler case of singleton demands has been established as a challenging computational task, when Hajiaghayi and Jain (SODA ’06) related its inapproximability to that of dense k -subgraph.In this paper, we present the first non-trivial approximation algorithm for k-generalized connectivity, which is derived by synthesizing several techniques originating in probabilistic embeddings of finite metrics, network design, and randomization. Specifically, our algorithm constructs, with constant probability, a feasible subgraph whose cost is within a factor of O(n ^2/3?polylog(n,k)) of optimal. We believe that the fundamental approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.     

On nonlinear multi-covering problems

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands \(\{d_0,\dots ,d_{n-1}\}\) and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly \(d_i\) subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).