A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time

The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5–1/2m)-competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.     

A hybrid artificial immune algorithm for a realistic variant of job shops to minimize the total completion time

This paper investigates an extended problem of job shop scheduling to minimize the total completion time. With aim of actualization of the scheduling problems, many researchers have recently considered realistic assumptions in their problems. Two of the most applied assumptions are to consider sequence-dependent setup times and machine availability constraints (MACs). In this paper, we deal with a specific case of MACs caused by preventive maintenance (PM) operations. Contrary to the previous papers considering fixed or/and conservative policies, we consider flexible PM operations, in which PM operations may be postponed or expedited as required. A simple technique is employed to schedule production jobs along with the flexible MACs caused by PM. To solve the given problem, we present a novel meta-heuristic method based on the artificial immune algorithm (AIA) incorporating some advanced features. For further enhancement, the proposed AIA is hybridized with a simple and fast simulated annealing (SA). To evaluate the proposed algorithms, we compare our proposed AIA with three well-known algorithms taken from the literature. Finally, we find that the proposed AIA outperforms other algorithms.     

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.     

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

Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times

This research deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The single machine robust scheduling problem (SMRSP) aims to obtain robust job sequences with minimum worst-case total flow time. We describe uncertain processing times using intervals, and adopt an uncertainty set that incorporates a budget parameter to control the degree of conservatism. A revision of the uncertainty set is also proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. A mixed integer linear program is developed for the SMRSP, where a linear program for determining the worst-case total flow time is integrated within the conventional integer program of the SMSP. To efficiently solve the SMRSP, a simple iterative improvement (SII) heuristic and a simulated annealing (SA) heuristic are developed. Experimental results demonstrate that the proposed SII and SA heuristics are effective and efficient in solving SMRSP with practical problem sizes.     

Hierarchical minimization of completion time variance and makespan in jobshops

This paper addresses the problem of minimizing makespan for a given set of n jobs to be processed on each of m machines in a static jobshop, subject to the minimum completion time variance (CTV). A lower bound on CTV is developed for the static jobshop problem. A backward scheduling approach is proposed using the observations on the development of lower bound for hierarchical minimization of CTV and makespan. A lower bound on makespan subject to minimum CTV is also presented for this problem. Finally, we present two simulated annealing heuristic approaches using the concepts of forward and backward scheduling. Their performances are compared against each other through the use of the lower bounds established in this work. The simulated annealing heuristic based on backward scheduling is shown to perform well by evaluating the developed heuristics on 82 jobshop problems taken from literature.     

Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints

This paper considers a deterministic scheduling problem where multiple jobs with s-precedence relations are processed on multiple identical parallel machines. The objective is to minimize the total completion time. The s-precedence relation between two jobs i and j represents the situation where job j is constrained from processing until job i starts processing, which is different from the standard definition of a precedence relation where j cannot start until i completes. The s-precedence relation has wide applicability in the real world such as first-come-first-served processing systems.     

Minimizing total weighted completion time under makespan constraint for two-agent scheduling with job-dependent aging effects

In this paper, we consider a two-agent single-machine scheduling problem with linear position-based aging effects and job-dependent aging ratios. The objective is to minimize the total weighted completion time of all jobs for two agents, where the makespan for one agent is constrained under an upper bound. After showing that this problem is at least NP-hard, we develop two solution algorithms: First, we devise a branch-and-bound algorithm to find an optimal solution through the establishment of several dominance and feasibility properties, and a lower bound. Second, we propose efficient simulated annealing algorithms, using three different methods to generate an initial solution. Through a numerical experiment, we demonstrate that the suggested algorithms can be applied to efficiently find near-optimal solutions within a reasonable amount of CPU time. In particular, we show that the initial solution method (arranging the jobs for one agent in non-increasing order of aging ratio, and scheduling the jobs for the other in the weighted shortest normal processing time order) is superior to others. Moreover, through scalability testing, we verify its consistent and relatively outstanding performance for larger systems with many processing jobs.     

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.     

Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm

In this study, a bi-objective multi-start simulated-annealing algorithm (BMSA) is presented for permutation flowshop scheduling problems with the objectives of minimizing the makespan and total flowtime of jobs. To evaluate the performance of the BMSA, computational experiments were conducted on the well-known benchmark problem set provided by Taillard. The non-dominated sets obtained from each of the existing benchmark algorithms and the BMSA were compared, and then combined to form a net non-dominated front. The computational results show that more than 64% of the solutions in the net non-dominated front are contributed by the proposed BMSA. It is believed that these solutions can serve as new benchmarks for future research.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

Minimizing total completion time for re-entrant flow shop scheduling problems

In this paper, we study re-entrant flow shop scheduling problems with the objective of minimizing total completion time. In a re-entrant scheduling problem, jobs may visit some machines more than once for processing. The problem is NP-hard even for machine number m=2. A heuristic algorithm is presented to solve the problem, in which an effective k-insertion technique is introduced as the improvement strategy in iterations. Computational experiments and analyses are performed to give guidelines of choosing parameters in the algorithm. We also provide a lower bound for the total completion time of the optimal solution when there are only two machines. Objective function values of the heuristic solutions are compared with the lower bounds to evaluate the efficiency of the algorithm. For randomly generated instances, the results show that the given heuristic algorithm generates solutions with total completion times within 1.2 times of the lower bounds in most of the cases.     

Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time

This paper addresses a sub-population based hybrid monkey search algorithm to solve the flow shop scheduling problem which has been proved to be non-deterministic polynomial time hard (NP-hard) type combinatorial optimization problems. Minimization of makespan and total flow time are the objective functions considered. In the proposed algorithm, two different sub-populations for the two objectives are generated and different dispatching rules are used to improve the solution quality. To the best of our knowledge, this is the first application of monkey search algorithm to solve the flow shop scheduling problems. The performance of the proposed algorithm has been tested with the benchmark problems addressed in the literature. Computational results reveal that the proposed algorithm outperforms many other heuristics and meta-heuristics addressed in the literature.     

A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time

This paper is about scheduling parallel jobs, i.e. which can be executed on more than one machine at the same time. Malleable jobs is a special class of parallel jobs. The number of machines a malleable job is executed on may change during its execution.In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of “ascending” schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed.We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.     

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.     

Robust scheduling on a single machine to minimize total flow time

In a real-world manufacturing environment featuring a variety of uncertainties, production schedules for manufacturing systems often cannot be executed exactly as they are developed. In these environments, schedule robustness that guarantees the best worst-case performance is a more appropriate criterion in developing schedules, although most existing studies have developed optimal schedules with respect to a deterministic or stochastic scheduling model. This study concerns robust single machine scheduling with uncertain job processing times and sequence-dependent family setup times explicitly represented by interval data. The objective is to obtain robust sequences of job families and jobs within each family that minimize the absolute deviation of total flow time from the optimal solution under the worst-case scenario. We prove that the robust single machine scheduling problem of interest is NP-hard. This problem is reformulated as a robust constrained shortest path problem and solved by a simulated annealing-based algorithmic framework that embeds a generalized label correcting method. The results of numerical experiments demonstrate that the proposed heuristic is effective and efficient for determining robust schedules. In addition, we explore the impact of degree of uncertainty on the performance measures and examine the tradeoff between robustness and optimality.     

Minimizing the total weighted completion time of deteriorating jobs

The paper deals with a single machine problem of scheduling jobs with start time dependent processing times to minimize the total weighted completion time. The computational complexity of this problem was unknown for ten years. We prove that the problem is NP-hard.     

Scheduling with flexible resources in parallel workcenters to minimize maximum completion time

In this paper we consider the parallel machine scheduling problem with dual resource constraints with the objective of minimizing the maximum completion time. We develop heuristics that combine list-scheduling and bin-packing approaches with rules to iteratively modify the flexible resource allocation. A lower bound is presented and the previous and proposed solution approaches to the problem are analyzed under a variety of experimental conditions, demonstrating that there are advantages to the proposed heuristics.