Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan

This study addresses a single machine scheduling problem with periodic maintenance, where the machine is assumed to be stopped periodically for maintenance for a constant time w during the scheduling period. Meanwhile, the maintenance period [u, v] is assumed to have been previously arranged and the time w is assumed not to exceed the available maintenance period [u, v] (i.e. w ? v − u). The time u(v) is the earliest (latest) time at which the machine starts (stops) its maintenance. The objective is to minimize the makespan. Two mixed binary integer programming (BIP) models are provided for deriving the optimal solution. Additionally, an efficient heuristic is proposed for finding the near-optimal solution for large-sized problems. Finally, computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The mixed BIP model can optimally solve up to 100-job instances, while the average percentage error of the heuristic is below 1%.     

A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects

This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. We consider the following objective functions: the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of minimization of the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Open shop scheduling problem to minimize makespan with release dates

The scheduling problem of open shop to minimize makespan with release dates is investigated in this paper. Unlike the usual researches to confirm the conjecture that the tight worst-case performance ratio of the Dense Schedule (DS) is 2 − 1/m, where m is the number of machines, the asymptotic optimality of the DS is proven when the problem scale tends to infinity. Furthermore, an on-line heuristic based on DS, Dynamic Shortest Processing Time-Dense Schedule, is presented to deal with the off-line and on-line versions of this problem. At the end of the paper, an asymptotically optimal lower bound is provided and the results of numerical experiments show the effectiveness of the heuristic.     

Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

This paper studies the single-machine scheduling problem with deteriorating jobs and learning considerations. The objective is to minimize the makespan. We first show that the schedule produced by the largest growth rate rule is unbounded for our model, although it is an optimal solution for the scheduling problem with deteriorating jobs and no learning. We then consider three special cases of the problem, each corresponding to a specific practical scheduling scenario. Based on the derived optimal properties, we develop an optimal algorithm for each of these cases. Finally, we consider a relaxed model of the second special case, and present a heuristic and analyze its worst-case performance bound.     

A note on “scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan”

In a recent paper, Chen [J.S. Chen, Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, European Journal of Operational Research 190 (2008) 90–102] proposes a heuristic algorithm to deal with the problem Scheduling of Nonresumable Jobs and Flexible Maintenance Activities on A Single Machine to Minimize Makespan  . Chen also provides computational results to demonstrate its effectiveness. In this note, we first show that the worst-case performance bound of this heuristic algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case performance bound less than 2 unless P=NP$P=\mathit{NP}$, which implies that Chen’s heuristic algorithm is the best possible polynomial time approximation algorithm for the considered scheduling problem.     

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.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

Learning effect and deteriorating jobs in the single machine scheduling problems

This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the k$k$th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively.     

Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B  , the problem remains strongly NP-hard when B?U$B?U$ for a variable U?2$U?2$ or B?U$B?U$ for any constant U?2$U?2$. For the case of B?U$B?U$, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U?2$U?2$. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.     

Single machine scheduling with truncated job-dependent learning effect

In this paper we consider the single machine scheduling problem with truncated job-dependent learning effect. By the truncated job-dependent learning effect, we mean that the actual job processing time is a function which depends not only on the job-dependent learning effect (i.e., the learning in the production process of some jobs to be faster than that of others) but also on a control parameter. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness and common (slack) due-date penalty, respectively. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption

In this paper, we consider the rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the maximum sequence disruption. We show that the considered problem can be solved in polynomial time.     

Single machine quadratic penalty function scheduling with deteriorating jobs and group technology

This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. We consider the case of jobs whose processing times are a simple linear function of their starting time. The two objectives of scheduling problems are to minimize the weighted sum of squared completion times and the weighted sum of squared waiting times, respectively. We also provide polynomial time algorithms to solve these problems.     

Single-machine scheduling problems with both deteriorating jobs and learning effects

In this paper we consider the single-machine scheduling problems with job-position-based and sum-of-processing-times based processing times. The real processing time of a job is a function of its position and the total processing time of the jobs that are in front of it in the sequence. The objective is to minimize the makespan, and to minimize the mean finish time. We prove that some special cases are polynomially solvable under some restrictions of the parameters. In addition, for some another special cases of minimization of the mean finish time and the makespan, we show that an optimal schedule is V-shaped with respect to job normal processing times. Then, we propose a heuristic based on the V-shaped property, and show through a computational experiment that it performs efficiently.     

On-line scheduling on a batch machine to minimize makespan with limited restarts

We study the on-line scheduling on an unbounded batch machine to minimize makespan. In this model, jobs arrive over time and batches are allowed limited restarts. Any batch that contains a job which has already been restarted once cannot be restarted any more. We provide a best possible on-line algorithm for the problem with a competitive ratio .