An iterative algorithm for scheduling UET tasks with due dates and release times

A new polynomial-time iterative algorithm is presented for the scheduling problem with a unit execution time task system, parallel identical processors, precedence constraints, release times, and the criterion of maximum lateness. For the maximum lateness and makespan problems the algorithm allows to achieve the performance guarantees previously known only for the problems without release times.     

A note on minimizing maximum lateness in a one-machine sequencing problem with release dates

This paper deals with the problem of minimizing maximum lateness on one machine with release dates. For this problem Carlier [1] suggests that if a schedule obtained by Schrage's algorithm is optimal, then there exists a set of jobs J such that the makespan of the Schrage schedule is equal to min _{i ε J}a_i + Σ_iεJd_i + min; _iϵJq_i where a_i, d_i and q_i is the release date, processing time and the tail of job i, respectively. In this paper a counterexample is given for this assertion. It is also shown that the assertion is true if the processing times of all the jobs are equal to one.     

Single-machine scheduling against due dates with past-sequence-dependent setup times

Recently Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] introduced past-sequence-dependent setup times to scheduling problems. This means that the setup time of a job is proportionate to the sum of processing times of the jobs already scheduled. Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] were able to show for a number of single-machine scheduling problems with completion time goals that they remain polynomially solvable. In this paper we extend the analysis to problems with due dates. We demonstrated that some problems remain polynomially solvable. However, for some other problems well-known polynomially solution approaches do not guarantee optimality any longer. Consequently we concentrated on finding polynomially solvable special cases.     

Scheduling with agreeable release times and due dates on a batch processing machine

We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modeled as batch processing machines. The job release times and due dates are assumed to be agreeable. Two different objective functions are considered: minimize the maximum tardiness and minimize the number of tardy jobs. We study the complexity of the problems. Efficient algorithms are also provided for the case when the job release times, due dates, and processing times are agreeable, which generalize those provided by Lee, Uzsoy and Martin-Vega (1992).     

A block approach for single-machine scheduling with release dates and due dates

The problem of scheduling jobs on a single machine subject to given release dates and due dates is considered. A new algorithm of the branch-and-bound type for solving this problem is proposed. The approach used in the paper is fully based on the eliminative properties of a block of jobs and in contradiction to the existing algorithms, it does not require any heuristic method to generate a current solution in a search tree. However, a heuristic may be used in order to obtain a good initial solution. Extensive computational experiments show a high efficiency of the algorithm.     

A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times

We consider a scheduling problem in which the processing time of each job deteriorates, i.e. it increases as time passes after the release date of the job. We present a dynamic programming algorithm coupled with upper bounding and lower bounding techniques to compute exact solutions. We report on problem instances of different size and we analyze the dependence between the ranges to which the data belong and the computing time.     

GA-Ensemble: a genetic algorithm for robust ensembles

Many simple and complex methods have been developed to solve the classification problem. Boosting is one of the best known techniques for improving the accuracy of classifiers. However, boosting is prone to overfitting with noisy data and the final model is difficult to interpret. Some boosting methods, including AdaBoost, are also very sensitive to outliers. In this article we propose a new method, GA-Ensemble, which directly solves for the set of weak classifiers and their associated weights using a genetic algorithm. The genetic algorithm utilizes a new penalized fitness function that limits the number of weak classifiers and controls the effects of outliers by maximizing an appropriately chosen $p$ th percentile of margins. We compare the test set error rates of GA-Ensemble, AdaBoost, and GentleBoost (an outlier-resistant version of AdaBoost) using several artificial data sets and real-world data sets from the UC-Irvine Machine Learning Repository. GA-Ensemble is found to be more resistant to outliers and results in simpler predictive models than AdaBoost and GentleBoost.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

A multi-objective genetic algorithm for robust flight scheduling using simulation

Traditional methods of developing flight schedules generally do not take into consideration disruptions that may arise during actual operations. Potential irregularities in airline operations such as equipment failure are not adequately considered during the planning stage of a flight schedule. As such, flight schedules cannot be met as planned and their performance is compromised, which may eventually lead to huge losses in revenue for airlines. In this paper, we seek to improve the robustness of a flight schedule by re-timing its departure times. The problem is modeled as a multi-objective optimization problem, and a multi-objective genetic algorithm (MOGA) is developed to solve the problem. To evaluate flight schedules, SIMAIR 2.0, a simulation model which simulates airline operations under operational irregularities, has been employed. The simulation results indicate that we are able to develop schedules with better operation costs and on-time performance through the application of MOGA.     

Designing robust liner shipping schedules: Optimizing recovery actions and buffer times

It is important for liner shipping companies to maintain cost efficient and robust liner shipping networks. Regularly, they set up pro-forma schedules, yet it is difficult to stay on time. We consider the problem of managing the delays. Therefore, we need to determine an optimal recovery policy and buffer time allocation to the ship route in order to minimize the total costs associated with delays and recovery actions, such as increasing sailing speed. We introduce a general framework consisting of a mixed integer programming formulation to solve discrete stochastic decision problems with short and long term decisions and apply this framework to the above described problem. Furthermore, we propose and test four heuristics for this problem. We compared the results of our method with an existing liner shipping route schedule and found a cost decrease of 28.9% after optimizing the buffer time distribution compared to the cost of sailing the current route schedule at constant speed.     

A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility

After 50 years of research in the field of flowshop scheduling problems the scientific community still observes a noticeable gap between the theory and the practice of scheduling. In this paper we aim to provide a metaheuristic, in the form of a genetic algorithm, to a complex generalized flowshop scheduling problem that results from the addition of unrelated parallel machines at each stage, sequence dependent setup times and machine eligibility. Such a problem is common in the production of textiles and ceramic tiles. The proposed algorithm incorporates new characteristics and four new crossover operators. We show an extensive calibration of the different parameters and operators by means of experimental designs. To evaluate the proposed algorithm we present several adaptations of other well-known and recent metaheuristics to the problem and conduct several experiments with a set of 1320 random instances as well as with real data taken from companies of the ceramic tile manufacturing sector. The results indicate that the proposed algorithm is more effective than all other adaptations.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times

In this work a genetic algorithm is presented for the unrelated parallel machine scheduling problem in which machine and job sequence dependent setup times are considered. The proposed genetic algorithm includes a fast local search and a local search enhanced crossover operator. Two versions of the algorithm are obtained after extensive calibrations using the Design of Experiments (DOE) approach. We review, evaluate and compare the proposed algorithm against the best methods known from the literature. We also develop a benchmark of small and large instances to carry out the computational experiments. After an exhaustive computational and statistical analysis we can conclude that the proposed method shows an excellent performance overcoming the rest of the evaluated methods in a comprehensive benchmark set of instances.     

A relaxation algorithm with a probabilistic guarantee for robust deviation optimization

Three measures of robustness (absolute robustness, deviation robustness and relative robustness), whose choice depends on the goals of the decision maker, have been proposed for uncertain optimization problems. Absolute robustness has been thoroughly studied, whereas the others have been studied to less of a degree.     

A multicriteria approach for optimizing bus schedules and school starting times

In many rural counties pupils on their way to school are a large, if not the largest group of customers for public mass transit. Hence an effective optimization of public mass transit in these regions must include the traffic caused by pupils. Besides a change in the schedules of the buses and the starting times of the trips, the school starting time may become an integral part of the planning process. We discuss the legal framework for this optimization problem in German states and counties and present a multi-objective mixed-integer linear programming formulation for the simultaneous specification of school and trip starting times. For its solution, we develop a two-stage decomposition heuristic and apply it to practical data sets from three different rural German counties.     

Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint

This paper focuses on the scheduling problem of minimizing makespan for a given set of jobs in a two-stage hybrid flowshop subject to a product-mix ratio constraint. There are identical parallel machines at the first stage of the hybrid flowshop, while there is a single batch-processing machine at the second stage. Ready times of the jobs (at the first stage) may be different, and a given product-mix ratio of job types should be kept in each batch at the second stage. We present three types of heuristic algorithms: forward scheduling algorithms, backward scheduling algorithms, and iterative algorithms. To evaluate performance of the suggested algorithms, a series of computational experiments are performed on randomly generated test problems and results are reported.     

A robust algorithm for identification of proteins in a database

In recent years, more and more algorithms and software for reconstruction of partial or entire amino acid sequences by the mass spectra of peptides appear. However, with rare exception, such sequences always contain errors due to many reasons like a chemical noise in the spectrum, incomplete fragmentation, etc. Posttranslational modifications of proteins cause additional difficulties. In this paper, we suggest a PepTiger algorithm, which can correctly identify peptides in a database by de novo sequences containing errors. The algorithm is based on the method of approximate string matching and a specially developed system of scoring, which takes into account the string distance between the de novo sequence and the sequence of the peptide candidate in the database, the difference between their masses, and the similarity between the experimental mass spectrum and the theoretical spectrum of the peptide candidate. The algorithm suggested here correctly identifies a larger number of de novo sequences than other algorithms for identification of peptides by their de novo sequences.     

A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem

This paper deals with the one-machine dynamic total completion time scheduling problem. This problem is known to be NP-hard in the strong sense. A polynomial time heuristic algorithm is proposed which applies the recently introduced Recovering Beam Search (RBS) approach. The algorithm is based on a beam search procedure with unitary beam width and includes a recovering subroutine that allows to overcome wrong decisions taken at higher levels of the beam search tree. It is shown that the total number of considered nodes is bounded by n where n is the jobsize. The proposed algorithm is able to solve in very short CPU time problems with up to 500 jobs outperforming the best state of the art heuristics.     

A fast algorithm for robust regression with penalised trimmed squares

The presence of groups containing high leverage outliers makes linear regression a difficult problem due to the masking effect. The available high breakdown estimators based on Least Trimmed Squares often do not succeed in detecting masked high leverage outliers in finite samples. An alternative to the LTS estimator, called Penalised Trimmed Squares (PTS) estimator, was introduced by the authors in Zioutas and Avramidis (2005) Acta Math Appl Sin 21:323–334, Zioutas et al. (2007) REVSTAT 5:115–136 and it appears to be less sensitive to the masking problem. This estimator is defined by a Quadratic Mixed Integer Programming (QMIP) problem, where in the objective function a penalty cost for each observation is included which serves as an upper bound on the residual error for any feasible regression line. Since the PTS does not require presetting the number of outliers to delete from the data set, it has better efficiency with respect to other estimators. However, due to the high computational complexity of the resulting QMIP problem, exact solutions for moderately large regression problems is infeasible. In this paper we further establish the theoretical properties of the PTS estimator, such as high breakdown and efficiency, and propose an approximate algorithm called Fast-PTS to compute the PTS estimator for large data sets efficiently. Extensive computational experiments on sets of benchmark instances with varying degrees of outlier contamination, indicate that the proposed algorithm performs well in identifying groups of high leverage outliers in reasonable computational time.     

A robust algorithm for generalized geometric programming

Most existing methods of global optimization for generalized geometric programming (GGP) actually compute an approximate optimal solution of a linear or convex relaxation of the original problem. However, these approaches may sometimes provide an infeasible solution, or far from the true optimum. To overcome these limitations, a robust solution algorithm is proposed for global optimization of (GGP) problem. This algorithm guarantees adequately to obtain a robust optimal solution, which is feasible and close to the actual optimal solution, and is also stable under small perturbations of the constraints.