A note on a single-machine lot scheduling problem with indivisible orders

In this paper, a lot scheduling problem on a single machine with indivisible orders is studied. The objective is to minimize the total completion time of all orders. We show that the problem is NP-hard in the strong sense. Then, a binary integer programming approach and four simple heuristics are proposed to solve the problem. The binary integer programming approach with running time limit is considered as one heuristic method. As compared to a lower bound, the average performances of the heuristic method are really good and better than those of the four simple heuristics.     

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.     

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.     

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.     

On scheduling a single machine with resource dependent release times

We consider a single machine scheduling problem with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. The objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. It is known that the problem is polynomially solvable in O(n⁴) with n the number of jobs.     

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.     

Pareto and scalar bicriterion optimization in scheduling deteriorating jobs

In the paper two problems of a single machine bicriterion scheduling of a set of deteriorating jobs are considered. The jobs are independent, nonpreemptable and are ready for processing at time 0$0$. The processing time _pj$p_j$ of each job is a linear function of the starting time _Sj$S_j$ of the job, _pj=1+_αjSj$p_j=1+{\alpha }_j{S}_j$, where _Sj?0$S_j?0$ and _αj>0${\alpha }_j>0$ for j=0,1,...,n$j=0,1,...,n$.     

Scheduling jobs on a single machine to maximize the total revenue of jobs

In today's hyper-competitive marketplace, many products like memory chips and computers are characterized by short life cycles and rapidly declining sales prices. This implies that the amount of revenue generated as a result of completing a product (job) may be decreasing as its completion time is delayed. In such an environment, there is a decided preference for the maximization of product revenues as an important objective. Based on the assumption that the decreasing rate of revenue is dependent on their product types, we intend to develop a searching algorithm and some heuristic algorithms to locate optimal and near-optimal job sequences, respectively, and thereby maximize total earned revenue.     

Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem

We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.     

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α−1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k−1)(n−2)/k(n+k−2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G.     

The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time

This work studies the scheduling problem where a set of jobs are available for processing in a no-wait and separate setup two-machine flow shop system with a single server. The no-wait constraint requires that the operations of a job have to be processed continuously without waiting between two machines. The setup time is incurred and attended by a single sever which can perform one setup at a time. The performance measure considered is the total completion time. The problem is strongly NP-hard. Optimal solutions for several restricted cases and some properties for general case are proposed. Both the heuristic and the branch and bound algorithms are established to tackle the problem. Computational experiments indicate that the heuristic and the branch and bound algorithm are superior to the existing ones in term of solution quality and number of branching nodes, respectively.     

An O(n 2 ) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n²) time algorithm to solve the problem.     

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.     

A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity

This note considers a single machine scheduling and due-window assignment problem, in which the processing time of a job is a linear function of its starting time and the job-independent deterioration rates are identical for all jobs. We allow an option for performing a rate-modifying activity for changing the normal processing times of the jobs following this activity. The objective is to schedule the jobs, the due-window and the rate-modifying activity so as to minimize the sum of earliness, tardiness and due-window starting time and due-window size costs. We introduce a polynomial solution for the problem.     

Approximation results for a bicriteria job scheduling problem on a single machine without preemption

We study the problem of minimizing the average weighted completion time on a single machine under the additional constraint that the sum of completion times does not exceed a given bound B(1|∑Cj?B|∑wjCj) for which we propose a (2,1)-approximation algorithm. We also address the problem 1|∑cjCj?B|∑wjCj for which we present a (2,2)-approximation algorithm. After showing that the problem of minimizing two different sums of weighted completion times is intractable, we present an algorithm which computes a (2(1+?),1) (respectively (2(1+?),2))-approximate Pareto curve for the problem 1‖(∑Cj,∑wjCj) (respectively 1‖(∑cjCj,∑wjCj)).     

Unrelated parallel-machine scheduling with deteriorating maintenance activities

We study the problem of unrelated parallel-machine scheduling with deteriorating maintenance activities. Each machine has at most one maintenance activity, which can be performed at any time throughout the planning horizon. The length of the maintenance activity increases linearly with its starting time. The objective is to minimize the total completion time or the total machine load. We show that both versions of the problem can be optimally solved in polynomial time.     

Note on “Unrelated parallel-machine scheduling with deteriorating maintenance activities”

In this note, we prove that both problems studied by Cheng et al. [Cheng, T. C. E., Hsu, C.-J., & Yang, D.-L. (2011). Unrelated parallel-machine scheduling with deteriorating maintenance activities. Computers and Industrial Engineering, 60, 602–605] can be solved in O(n^m+3) time no matter what the processing time of a job after a maintenance activity is greater or less than its processing time before the maintenance activity, where m is the number of machines and n is the number of jobs.     

Single machine scheduling problems with resource dependent release times

We consider two single machine scheduling problems with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. In the first problem, the objective is to minimize the total resource consumption with a constraint on the sum of job completion times. We show that a recognition version of the problem is NP-complete. In the second problem, the objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. We provide some optimality conditions and show that the problem is polynomially solvable.     

Integrated production and preventive maintenance scheduling for a single machine with failure uncertainty

This paper addresses the problem of finding a robust and stable schedule for a single machine with availability constraints. The machine suffers unexpected breakdowns and follows the Weibull failure function. A joint model for integrating run-based preventive maintenance (PM) into the production scheduling problem is proposed, in which the sequence of jobs, the PM times and the planned completion times of jobs are proactively determined simultaneously. Aiming at optimizing the bi-objective of system robustness and stability, a genetic algorithm based on the properties of the optimal schedule is proposed. The experimental results demonstrate that the proposed algorithm is efficient and effective under practical problem sizes. In addition, the impact of degree of uncertainty on the performance and the tradeoff between robustness and stability are explored in detail.