Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single-machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose two new lower bounds that can be, respectively, computed in O(n²) and in O(nlogn) time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch-and-bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.     

Simulated-annealing heuristics for the single-machine scheduling problem with learning and unequal job release times

In scheduling of batch processing machines in the diffusion and oxidation areas of a wafer fabrication facility, it can be found that the processing times of these batching operations can be extremely long (10 h) when compared to other operations (1-2 h) in a wafer fab. Moreover, the jobs to be processed may have different priorities/weights, due dates and ready times. In the presence of unequal ready times, it would be better to wait for future job arrivals in order to increase the fullness of the batch. On the other hand, repeated processing of similar tasks improves workers’ skills. Motivated by these observations, we consider a single-machine problem with the sum of processing times based learning effect and release times. The objective is to find a schedule to minimize the total completion times. We first develop a branch-and-bound algorithm for the optimal solution. Then we propose a simulated-annealing heuristic algorithm for a near-optimal solution. Finally, we conduct a computational experiment to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 24 jobs, and the average error percentage of the simulated-annealing algorithm is less than 0.1482%.     

Two-agent singe-machine scheduling with release times to minimize the total weighted completion time

In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases.     

Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates

In this paper we consider the well-known single machine scheduling problem with release dates and minimization of the total job completion time. For solving this problem, denoted by 1|r_j|∑C_j, we provide a new metaheuristic which is an extension of the so-called filtered beam search proposed by Ow and Morton [30]. This metaheuristic, referred to as a Genetic Recovering Beam Search (GRBS), takes advantages of a Genetic Local Search (GLS) algorithm and a Recovering Beam Search (RBS) in order to efficiently explore the solution space. In this paper we present the GRBS framework and its application to the 1|r_j|∑C_j problem. Computational results show that it consistently yields optimal or near-optimal solutions and that it provides interesting results by comparison to GLS and RBS algorithms. Moreover, these results highlight that the proposed algorithm outperforms the state-of-the-art heuristics.     

Single machine scheduling problem with interval processing times to minimize mean weighted completion time

The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.     

The two-stage assembly scheduling problem to minimize total completion time with setup times

We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard, and therefore we present a dominance relation and propose three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is known to perform well for such problems. A new version of the latter heuristic, which utilizes the dominance relation, is proposed and shown to perform much better than the other two heuristics.     

Minimizing the makespan on a single machine with learning and unequal release times

The importance of the ready times can be found in Wafer fabrication with the presence of unequal ready times. It is sometimes advantageous to form a non-full batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. On the other hand, there is a significant involvement of humans in scheduling environments; the amount of learning activities is high. Hence it seems to be reasonable to consider learning in scheduling environments. However, research with learning and release times is relatively unexplored. Motivated by this observation, this paper deals with a single-machine problem with the learning effect and release times where the objective is to minimize the makespan. This paper proposes a branch-and-bound algorithm and three two-stage heuristic algorithms for the problem. The computational experiments show that the branch-and-bound algorithm can solve instances up to 25 jobs, and the best one with the average error percentage of the proposed heuristics is less than 0.05%.     

Exact and parallel metaheuristic algorithms for the single processor total weighted completion time scheduling problem with the sum-of-processing-time based models

In this paper, the single processor scheduling problem to minimize the total weighted completion times is analysed, where the processing times of jobs are described by functions dependent on the sum of the normal processing times of previously processed jobs, which can model learning or aging (deteriorating) effects. We construct the exact pseudopolynomial time algorithm based on the dynamic programming, which solves the problem, where the processing time of each job is described by an arbitrary stepwise function. Moreover, the parallel metaheuristic algorithms are provided for the general version of the problem with arbitrary sum-of-processing time based models. The efficiency of the proposed algorithms is evaluated during numerical analysis.     

Two-machine flowshop scheduling with truncated learning to minimize the total completion time

Scheduling with learning effects has received a lot of research attention lately. However, the flowshop setting is relatively unexplored. On the other hand, the actual processing time of a job under an uncontrolled learning effect will drop to zero precipitously as the number of jobs increases. This is rather absurd in reality. Motivated by these observations, we consider a two-machine flowshop scheduling problem in which the actual processing time of a job in a schedule is a function of the job’s position in the schedule and a control parameter of the learning function. The objective is to minimize the total completion time. We develop a branch-and-bound and three simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose some dominance properties and two lower bounds. We also present an efficient heuristic. A branch-and-bound algorithm, in which the heuristic, the lower bounds and the dominance properties are incorporated, is proposed and tested on a large set of randomly generated instances.     

The single-machine total weighted tardiness scheduling problem with position-based learning effects

This study addresses the problem of minimizing the total weighted tardiness on a single-machine with a position-based learning effect. Several dominance properties are established to develop branch and bound algorithm and a lower bound is provided to derive the optimal solution. In addition, three heuristic procedures are developed for near-optimal solutions. Computational results are also presented to evaluate the performance of the proposed algorithms.     

Genetic algorithms for a two-agent single-machine problem with release time

Scheduling with two competing agents has drawn a lot of attention lately. However, it is assumed that all the jobs are available in the beginning in most of the research. In this paper, we study a single-machine problem in which jobs have different release times. The objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound. Three genetic algorithms are proposed to obtain the near-optimal solutions. Computational results show that the branch-and-bound algorithm could solve most of the problems with 16 jobs within a reasonable amount of time. In addition, it shows that the performance of the combined genetic algorithm is very good with mean error percentages of less than 0.2% for all the cases.     

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%.     

Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

Optimizing blocking flow shop scheduling problem with total completion time criterion

The blocking flow shop scheduling problem has found many applications in manufacturing systems. There are a few exact methods for solving this problem with different criteria. In this paper, efforts will be made to optimize the total completion time criterion for this problem. We present two mixed binary integer programming models, one of which is based on the departure times of jobs from machines, and the other is based on the idle and blocking times of jobs. An initial upper bound generator and some lower bounds and dominance rules are also developed to be used in a branch and bound algorithm. The algorithm solves 17 instances of the Taillard's benchmark problem set in less than 20 min.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.     

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

A simple linear time algorithm for scheduling with step-improving processing times

We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line approximation algorithm and prove its worst-case performance guarantee.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.