A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs

The problem of scheduling on a single machine is considered in this paper with the objective of minimizing the sum of weighted tardiness of jobs. A new ant-colony optimization (ACO) algorithm, called fast ACO (FACO), is proposed and analysed for solving the single-machine scheduling problem. By considering the benchmark problems available in the literature for analysing the performance of algorithms for scheduling on a single machine with the consideration of weighted tardiness of jobs, we validate the appropriateness of the proposed local-search schemes and parameter settings used in the FACO. We also present a comparison of the requirements of CPU time for solving the single-machine total-weighted tardiness problem by the FACO and the existing algorithms.     

Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed

This paper considers two single-machine scheduling problems with outsourcing allowed where each job can be either processed on an in-house single-machine or outsourced. They include the problem of minimizing maximum lateness and outsourcing costs, and that of minimizing total tardiness and outsourcing costs. Outsourcing is commonly required as a way to improve productivity in various companies including electronics industries and motor industries. The objective is to minimize the weighted sum of the outsourcing cost and the scheduling measure represented by either one of maximum lateness and total tardiness, subject to outsourcing budget. It is proved that the problem is NP-hard. Some solution properties are characterized to derive heuristic algorithms, and also a branch-and-bound algorithm. Numerical experiments are conducted to evaluate performance of the derived algorithms.     

An exact algorithm for the precedence-constrained single-machine scheduling problem

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors’ previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness–tardiness problems, and most instances with 100 jobs of the former problem.     

Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.     

A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems

We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.     

Branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime,weighted tardiness and weighted earliness of jobs

The problem of scheduling in permutation flowshops is considered in this paper with the objectives of minimizing the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, with each objective considered separately. Lower bounds on the given objective (corresponding to a node generated in the scheduling tree) are developed by solving an assignment problem. Branch-and-bound algorithms are developed to obtain the best permutation sequence in each case. Our algorithm incorporates a job-based lower bound (integrated with machine-based bounds) with respect to the weighted flowtime/weighted tardiness/weighted flowtime and weighted tardiness, and a machine-based lower bound with respect to the weighted earliness of jobs. The proposed algorithms are evaluated by solving many randomly generated problems of different problem sizes. The results of an extensive computational investigation for various problem sizes are presented. In addition, one of the proposed branch-and-bound algorithms is compared with a related existing branch-and-bound algorithm.     

Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date

This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems. From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties.     

An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem

Based on the work by Congram, Potts and Van de Velde, we develop for the single-machine total weighted tardiness scheduling problem an enhanced dynasearch neighborhood obtained by the generalized pairwise interchange (GPI) operators. Despite of the wider neighborhood considered, a fast search procedure using also elimination criteria is developed. The computational results significantly improve over those of Congram, Potts and Van de Velde.     

Single-machine scheduling with both deterioration and learning effects

This paper considers a single-machine scheduling problem with both deterioration and learning effects. The objectives are to respectively minimize the makespan, the total completion times, the sum of weighted completion times, the sum of the kth power of the job completion times, the maximum lateness, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalties. Several polynomial time algorithms are proposed to optimally solve the problem with the above objectives.     

关于具有主次指标的单机排序的注记

本文讨论具有主次指标的单机同工期排序问题,其主指标和次指标取为:最大误时、总流程、误时工件数、总误时、加权总流程、加权误时工件数以及加权总误时。     

Two due date assignment problems in scheduling a single machine

We study two single-machine scheduling problems: minimizing the sum of weighted earliness, tardiness and due date assignment penalties and minimizing the weighted number of tardy jobs and due date assignment costs. We prove that both problems are strongly NP-hard and give polynomial solutions for some important special cases.     

On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.     

Multicriteria scheduling optimization using an elitist multiobjective population heuristic: the h-NSDE algorithm

In today’s manufacturing industry more than one performance criteria are considered for optimization to various degrees simultaneously. To deal with such hard competitive environments it is essential to develop appropriate multicriteria scheduling approaches. In this paper consideration is given to the problem of scheduling n independent jobs on a single machine with due dates and objective to simultaneously minimize three performance criteria namely, total weighted tardiness (TWT), maximum tardiness and maximum earliness. In the single machine scheduling literature no previous studies have been performed on test problems examining these criteria simultaneously. After positioning the problem within the relevant research field, we present a new heuristic algorithm for its solution. The developed algorithm termed the hybrid non-dominated sorting differential evolution (h-NSDE) is an extension of the author’s previous algorithm for the single-machine mono-criterion TWT problem. h-NSDE is devoted to the search for Pareto-optimal solutions. To enable the decision maker for evaluating a greater number of alternative non-dominated solutions, three multiobjective optimization approaches have been implemented and tested within the context of h-NSDE: including a weighted-sum based approach, a fuzzy-measures based approach which takes into account the interaction among the criteria as well as a Pareto-based approach. Experiments conducted on existing data set benchmarks problems show the effect of these approaches on the performance of the h-NSDE algorithm. Moreover, comparative results between h-NSDE and some of the most popular multiobjective metaheuristics including SPEA2 and NSGA-II show clear superiority for h-NSDE in terms of both solution quality and solution diversity.     

A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity

The scheduling of maintenance activities has been extensively studied, with most studies focusing on single-machine problems. In real-world applications, however, multiple machines or assembly lines process numerous jobs simultaneously. In this paper, we study a parallel-machine scheduling problem in which the objective is to minimize the total tardiness given that there is a maintenance activity on each machine. We develop a branch-and-bound algorithm to solve the problem with a small problem size. In addition, we propose a hybrid genetic algorithm to obtain the approximate solutions when the number of jobs is large. The performance of the proposed algorithms is evaluated based mainly on computational results.     

Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.     

加工时间恶化的两个成组加工排序问题

This paper considers single-machine scheduling problems in group technology with the jobs‘ processing times being simple linear functions of their start times. The objective functions are the minimizing of makespan and total weighted completion time. Some optimal conditions and algorithms are given and the fact that the problem of total weighted completion times is NP-hard is proved.     

Single-machine scheduling with accelerating deterioration effects

Scheduling with deterioration effects has been widely investigated in the past two decades. In realistic situations, the deterioration effect might accelerate, especially in the food manufacturing industry. In this paper we propose a scheduling model with an accelerating deterioration effect. We show that the single-machine problems under the model to minimize the makespan, total completion time, total weighted completion time, maximum lateness, maximum tardiness, and total tardiness remain polynomially solvable.     

A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem

We extend the dynasearch technique, recently proposed by Congram et al., in the context of time-dependent combinatorial optimization problems. As an application we consider a general time-dependent (idleness) version of the well known single-machine total weighted tardiness scheduling problem, in which the processing time of a job depends on its starting time of execution. We develop a multi-start local search algorithm and present experimental results on several types of instances showing the superiority of the dynasearch neighborhood over the traditional one.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

Single-machine scheduling problems with actual time-dependent and job-dependent learning effect

In this study, we introduce an actual time-dependent and job-dependent learning effect into single-machine scheduling problems. We show that the complexity results of the makespan minimization problem and the sum of weighted completion time minimization problem are all NP-hard. The complexity result of the maximum lateness minimization problem is NP-hard in the strong sense. We also provide three special cases which can be solved by polynomial time algorithms.