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.     

Variable neighborhood search for minimum cost berth allocation

The berth allocation problem is to allocate space along the quayside to incoming ships at a container terminal in order to minimize some objective function. We consider minimization of total costs for waiting and handling as well as earliness or tardiness of completion, for all ships. We assume ships can arrive at any given time, i.e., before or after the berths become available. The resulting problem, which subsumes several previous ones, is expressed as a linear mixed 0–1 program. As it turns out to be too time-consuming for exact solution of instances of realistic size, a Variable Neighborhood Search (VNS) heuristic is proposed, and compared with Multi-Start (MS), a Genetic Search algorithm (GA) and a Memetic Search algorithm (MA). VNS provides optimal solutions for all instances solved to optimality in a previous paper of the first two authors and outperforms MS, MA and GA on large instances.     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

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.     

Single machine scheduling with randomly compressible processing times

This work is concerned with single machine scheduling with random compression of processing times. The objective is to find the optimal sequence to minimize the cost based on earliness, tardiness and compression. The analysis is carried out under a common due date. Both absolute derivation cost and squared derivation cost are considered. For both constrained problems and unconstrained problems, it is shown that an optimal schedule must be V-shaped. Remarks on common slack model is also provided.     

A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties

In this paper, a hybrid genetic algorithm is developed to solve the single machine scheduling problem with the objective to minimize the weighted sum of earliness and tardiness costs. First, dominance properties of (the conditions on) the optimal schedule are developed based on the switching of two adjacent jobs i and j. These dominance properties are only necessary conditions and not sufficient conditions for any given schedule to be optimal. Therefore, these dominance properties are further embedded in the genetic algorithm and we call it genetic algorithm with dominance properties (GADP). This GADP is a hybrid genetic algorithm. The initial populations of schedules in the genetic algorithm are generated using these dominance properties. GA can further improve the performance of these initial solutions after the evolving procedures. The performances of hybrid genetic algorithm (GADP) have been compared with simple genetic algorithm (SGA) using benchmark instances. It is shown that this hybrid genetic algorithm (GADP) performs very well when compared with DP or SGA alone.     

Scheduling identical jobs and due-window on uniform machines

We extend a classical common due-window assignment problem to a setting of parallel uniform machines. Jobs are assumed to have identical processing times. The objective is minimum earliness, tardiness, due-window starting time, and due-window size. We focus on the case of two machines. Despite the many (12) candidate schedules for optimality, an efficient constant time solution is introduced.     

Minimizing earliness and tardiness costs in stochastic scheduling

We address the single-machine stochastic scheduling problem with an objective of minimizing total expected earliness and tardiness costs, assuming that processing times follow normal distributions and due dates are decisions. We develop a branch and bound algorithm to find optimal solutions to this problem and report the results of computational experiments. We also test some heuristic procedures and find that surprisingly good performance can be achieved by a list schedule followed by an adjacent pairwise interchange procedure.     

Scheduling problems with random processing times under expected earliness/tardiness costs

This work is concerned with scheduling problems for a single machine. Taking earliness and tardiness of completion time and due–date value into consideration, the objective function with a common due date is considered. The processing time of each job is random. Sufficient conditions guaranteeing an optimal SEPT sequence are derived. Under exponential and normal processing times, further results are obtained     

Scheduling problems with two competing agents to minimize minmax and minsum earliness measures

A relatively new class of scheduling problems consists of multiple agents who compete on the use of a common processor. We focus in this paper on a two-agent setting. Each of the agents has a set of jobs to be processed on the same processor, and each of the agents wants to minimize a measure which depends on the completion times of its own jobs. The goal is to schedule the jobs such that the combined schedule performs well with respect to the measures of both agents. We consider measures of minmax and minsum earliness. Specifically, we focus on minimizing maximum earliness cost or total (weighted) earliness cost of one agent, subject to an upper bound on the maximum earliness cost of the other agent. We introduce a polynomial-time solution for the minmax problem, and prove NP-hardness for the weighted minsum case. The unweighted minsum problem is shown to have a polynomial-time solution.