Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

Motivated by a real-life scheduling problem in a steel wire factory in China,this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood)properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search.Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

A note on the precedence-constrained class sequencing problem

We give a short proof of a result of Tovey [Non-approximability of precedence-constrained sequencing to minimize setups, Discrete Appl. Math. 134:351-360, 2004] on the inapproximability of a scheduling problem known as precedence-constrained class sequencing. In addition, we present an approximation algorithm with performance guarantee (c+1)/2, where c is the number of colors. This improves upon Tovey's c-approximation.     

An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups

This paper addresses a single machine sequencing problem with variable processing times and sequence-dependent setups. The objective is to find the best trade-off between the JIT goal and the processing time compression and extension costs by simultaneously determining the job sequence and processing times for concerned jobs. Due to the combinatorial nature of the problem, it cannot be optimally solved in polynomial time. A tabu search approach is used to provide good and quick solutions. To improve the computational efficiency, an adaptive neighbourhood generation method is proposed and used in the tabu search algorithm. A total of 100 problems of different sizes have been solved to test the proposed approach. Our computational experience shows that the adaptive approach outperforms several other neighbourhood generation methods in terms of both convergence rate and solution quality. The effects of the search parameters are also discussed.     

On a pattern sequencing problem to minimize the maximum number of open stacks

Consider a wood cutting setting where different panels have to be cut from large boards. Each cut panel size is put into a stack which remains opened until the last panel of that size is cut. The problem considered here deals with the sequencing of the patterns in order to minimize the maximum number of open stacks during the production run. A branch and bound method for solving this problem is presented which uses a greedy type scheme to select the next node to branch.     

An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness

This paper presents several procedures for developing non-delay schedules for a permutation flow shop with family setups when the objective is to minimize total earliness and tardiness. These procedures consist of heuristics that were found to be effective for minimizing total tardiness in flow shops without family setups, modified to consider family setups and the total earliness and tardiness objective. These procedures are tested on several problem sets with varying conditions. The results show that variable greedy algorithms are effective when solving small problems, but using a genetic algorithm that includes a neighbourhood defined by the sequence of batches of jobs belonging to the same set-up family is effective when solving medium- or large-sized problems. The results also show that if setup times can be reduced a significant reduction in total earliness and tardiness could result.     

A pegging approach to the precedence-constrained knapsack problem

The knapsack problem (KP) is generalized to the case where items are partially ordered through a set of precedence relations. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be packed in the knapsack. However, each item can be accepted only when all the preceding items have been included in the knapsack. The knapsack problem with these additional constraints is referred to as the precedence-constrained knapsack problem (PCKP). To solve PCKP exactly, we present a pegging approach, where the size of the original problem is reduced by applying the Lagrangian relaxation followed by a pegging test. Through this approach, we are able to solve PCKPs with thousands of items within a few minutes on an ordinary workstation.     

An algorithm for single machine sequencing with deadlines to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine. Each job becomes available for processing at time zero, has a deadline by which it must be completed and has a positive weight. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is presented which incorporates lower bounds that are obtained using a new technique called the multiplier adjustment method. Firstly several dominance conditions are derived. Then a heuristic is described and sufficient conditions for its optimality are given. The lower bound is obtained by performing a Lagrangean relaxation of the deadline constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimal solution of the relaxed problem, thus yielding a lower bound. The algorithm is tested on problems with up to fifty jobs.     

An algorithm for single machine sequencing with release dates to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. Each job becomes available for processing at its release date, requires a processing time and has a positive weight. Given a processing order of the jobs, the earliest completion time for each job can be computed. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is derived. Firstly a heuristic is presented which is used in calculating the lower bound. Then the lower bound is obtained by performing a Lagrangean relaxation of the release date constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimum solution of the relaxed problem thus yielding a lower bound. A method to increase the lower bound by deriving improved constraints to replace the original release date constraints is given. The algorithm, which includes several dominance rules, is tested on problems with up to fifty jobs. The computational results indicate that the version of the lower bound using improved constraints is superior to the original version.     

Knapsack problems with setups

Knapsack problems with setups find their application in many concrete industrial and financial problems. Moreover, they also arise as subproblems in a Dantzig–Wolfe decomposition approach to more complex combinatorial optimization problems, where they need to be solved repeatedly and therefore efficiently. Here, we consider the multiple-class integer knapsack problem with setups. Items are partitioned into classes whose use implies a setup cost and associated capacity consumption. Item weights are assumed to be a multiple of their class weight. The total weight of selected items and setups is bounded. The objective is to maximize the difference between the profits of selected items and the fixed costs incurred for setting-up classes. A special case is the bounded integer knapsack problem with setups where each class holds a single item and its continuous version where a fraction of an item can be selected while incurring a full setup. The paper shows the extent to which classical results for the knapsack problem can be generalized to these variants with setups. In particular, an extension of the branch-and-bound algorithm of Horowitz and Sahni is developed for problems with positive setup costs. Our direct approach is compared experimentally with the approach proposed in the literature consisting in converting the problem into a multiple choice knapsack with pseudo-polynomial size.     

Vertex downgrading to minimize connectivity

Mathematical Programming - We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given...     

Stock cutting to minimize cutting length

In this paper we investigate the following problem: Given two convex P_in, and P_out where P_in is completely contained in P_out, we wish to find a sequence of ‘guillotine cuts’ to cut out P_in from P_out such that the total length of the cutting sequence is minimized. This problem has applications in stock cutting where a particular shape or design (in this case the polygon P_in) needs to be cut out of a given piece of parent material (the polygon P_out) using only guillotine cuts and where it is desired to minimize the cutting sequence length to improve the cutting time required per piece. We first prove some properties of the optimal solution to the problem and then give an approximation scheme for the problem that, given an error range δ, produces a cutting sequence whose total length is atmost δ more than that of the optimal cutting sequence. Then it is shown that this problem has optimal solutions that lie in the algebraic extension of the field that the input data belongs to — hence due to this algebraic nature of the problem, an approximation scheme is the best that can be achieved. Extensions of these results are also studied in the case where the polygons P_in and P_out are non-convex.     

Routing vehicles to minimize fuel consumption

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.     

Optimal investment to minimize the probability of drawdown

We determine the optimal investment strategy in a Black–Scholes financial market to minimize the so-called probability of drawdown, namely, the probability that the value of an investment portfolio reaches some fixed proportion of its maximum value to date. We assume that the portfolio is subject to a payout that is a deterministic function of its value, as might be the case for an endowment fund paying at a specified rate, for example, at a constant rate or at a rate that is proportional to the fund’s value.     

Designing routes to minimize fleet operating costs

A route-planner must try to schedule the delivaries by a fleet of vehicles such that customer requirements are met and management objectives are satisfied. In most cases, the number of feasible arrangements is legion, and calculations relating to individual vehicle loads, mileages, delivery times, etc. are tedious, allowing only a small fraction of possible route plans to be established and compared. The problem presents an ideal opportunity for computer application, not least to ensure that solutions are timely and error free.Several algorithms have been developed to improve the quality of vehicle routes, but in practice only those that rely on simple selection rules have found widespread acceptance, due to the innate complexity of the calculations that follow from a more rigorous approach and to the great variety of customer, vehicle, and operational characteristics that distinguish transport systems and which must be accomodated.The method presented here is based upon the well-known ‘savings’ criterion, but avoids many of its deficiencies by employing a random selection mode and producing (efficiently) a large sample of schedules from which to choose the most suitable. In particular, this allows greater flexibility in defining management objectives, and has led to substantial reductions in both fleet sizes and distances travelled, compared to published results, for a set of nine test cases each involving more than 200 customer locations.     

Using delayed damping to minimize transmitted vibrations

In Mokni et al. [Mokni L, Belhaq M, Lakrad F. Effect of fast parametric viscous damping excitation on vibration isolation in sdof systems. Commun Nonlinear Sci Numer Simulat 2011;16:1720-1724], it was shown that in a single degree of freedom system a fast nonlinear parametric damping enhances vibration isolation with respect to the case where the nonlinear damping is time-independent. The present work proposes additional enhancement of vibration isolation using delayed nonlinear damping. Attention is focused on assessing the contribution of a delayed nonlinear damping over a fast parametric damping in terms of minimizing transmissibility. The results show that a nonlinear damping with delay greatly improves vibration isolation.     

Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.