Note on minimizing total tardiness in a two-machine flowshop

This note considers the problem of sequencing jobs to minimize total tardiness in a two-machine flowshop. The note shows how three dominance conditions and a lower bound previously developed for this problem can be improved. The note also proposes a new dominance condition. A branch-and-bound algorithm is developed that uses the improvements and new dominance condition. The algorithm is tested on randomly generated problems and the results of the test show that the improvements and new dominance condition improves the branch-and-bound algorithm's efficiency.     

Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations

In many situations, a worker’s ability improves as a result of repeating the same or similar task; this phenomenon is known as the “learning effect”. In this paper, the learning effect is considered in a single-machine maximum lateness minimization problem. A branch-and-bound algorithm, incorporating several dominance properties, is provided to derive the optimal solution. In addition, two heuristic algorithms are proposed for this problem. The first one is based on the earliest due date (EDD) rule and a pairwise neighborhood search. The second one is based on the simulated annealing (SA) approach. Our computational results show that the SA algorithm is surprisingly accurate for a small to medium number of jobs. Moreover, the SA algorithm outperforms the traditional heuristic algorithm in terms of quality and execution time for a large number of jobs.     

Scheduling two-machine no-wait open shops to minimize makespan

This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.     

Two-machine flow shop scheduling with linear decreasing job deterioration

In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions.     

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times

This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.     

Exact algorithms for single-machine scheduling with time windows and precedence constraints

We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unit-time delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branch-and-bound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving medium-sized instances, and that it compares favorably with existing methods for special cases of the problem.     

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

Single machine weighted earliness–tardiness penalty problem with a common due date

In this paper, we have considered a class of single machine job scheduling problems where the objective is to minimize the weighted sum of earliness–tardiness penalties of jobs. The weights are job-independent but they depend on whether a job is early or tardy. The restricted version of the problem where the common due date is smaller than a critical value, is known to be NP-complete. While dynamic programming formulation runs out of memory for large problem instances, depth-first branch-and-bound formulation runs slow for large problems since it uses a tree search space. In this paper, we have suggested an algorithm to optimally solve large instances of the restricted version of the problem. The algorithm uses a graph search space. Unlike dynamic programming, the algorithm can output optimal solutions even when available memory is limited. It has been found to run faster than dynamic programming and depth-first branch-and-bound formulations and can solve much larger instances of the problem in reasonable time. New upper and lower bounds have been proposed and used. Experimental findings are given in detail.Scope and purposeA class of single machine problems arising out of scheduling jobs in JIT environment has been considered in this paper. The objective is to minimize the total weighted earliness–tardiness penalties of jobs. In this paper, we have presented a new algorithm and conducted extensive empirical runs to show that the new algorithm performs much better than the existing approaches in solving large instances of the problem.     

Single-machine batch delivery scheduling with job release dates,due windows and earliness,tardiness, holding and delivery costs

This paper deals with a single-machine scheduling problem in which jobs are released in different points in time but delivered to customers in batches. A due window is associated with each job. The objective is to schedule the jobs, to form them into batches and to decide the delivery date of each batch so as to minimize the sum of earliness, tardiness, holding, and delivery costs. A mathematical model of the problem is presented, and a set of dominance properties is established. To solve this NP-hard problem efficiently, a solution method is then proposed by incorporating the dominance properties with an imperialist competitive algorithm. Unforced idleness and forming discontinuous batches are allowed in the proposed algorithm. Moreover, the delivery date of a batch may be decided to be later than the completion time of the last job in the batch. Finally, computational experiments are conducted to evaluate the proposed model and solution procedure, and results are discussed.     

Trade-off solutions in a single-machine scheduling problem for minimizing total earliness and maximum tardiness

This paper considers a single-machine scheduling problem involving minimization of the total earliness and the maximum tardiness. Four dominant properties for the precedence relationship between jobs in a search for an optimal solution are proposed. The lower bounds of the total earliness and the maximum tardiness of a subproblem are derived. The dominance properties and the lower bounds are implemented in the branchand-bound algorithm to facilitate the search for an optimal schedule. A heuristic algorithm is then developed to overcome the inefficiency of the branch-and-bound algorithm. Computational performance of the two algorithms is also investigated.     

Parallel machine scheduling with precedence constraints and setup times

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. These problems are strongly NP-hard and it is even conjectured that no list scheduling algorithm can be defined without explicitly considering jointly scheduling and resource allocation. We propose dominance conditions based on the analysis of the problem structure and an extension to setup times of the energetic reasoning constraint propagation algorithm. An exact branch-and-bound procedure and a climbing discrepancy search (CDS) heuristic based on these components are defined. We show how the proposed dominance rules can still be valid in the CDS scheme. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.     

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

Two branch-and-bound algorithms for the robust parallel machine scheduling problem

Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.     

A single-machine bi-criterion learning scheduling problem with release times

The learning effect in scheduling has received considerable attention recently. However, most researchers consider a single criterion with the assumption that jobs are all ready to be processed. The research of bi-criterion problems with learning effect is relatively limited. This paper studies a single-machine learning effect scheduling problem with release times where the objective is to minimize the sum of makespan and total completion time. First, we develop a branch-and-bound algorithm incorporating with several dominance properties and a lower bound to derive the optimal solution. Secondly, we propose a genetic algorithm to obtain near-optimal solutions. Finally, a computational experiment is conducted to evaluate the performance of the branch-and-bound and the genetic algorithms.     

A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs

In this paper we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job we mean that the job's processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of time. The objective is to find a sequence that minimizes the total completion time of the jobs. For the general case, we derive several dominance properties, some lower bounds, and an initial upper bound by using a heuristic algorithm, and apply them to speed up the elimination process of a branch-and-bound algorithm developed to solve the problem.     

Common due date assignment and scheduling with ready times

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Scope and purpose

We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.     

Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.     

A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.     

A tabu method for a two-agent single-machine scheduling with deterioration jobs

In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.