Single-machine multitasking scheduling with job efficiency promotion

Motivated by behavioural and psychological phenomena that occur in human operators, we study single-machine multitasking scheduling with job efficiency promotion. In traditional multitasking scheduling, the primary task is assumed to be interrupted by every waiting task. In this paper we take into account job efficiency promotion that helps reduce the actual interruption time. We propose two functions to model job efficiency promotion based on the job positions in a given schedule. The objective is to minimize the makespan, total completion time, and total absolute difference in completion times. We show that the problem is polynomially solvable for each objective. We also provide efficient solutions for some special cases.

     

Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect

We study single machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect. In the general truncated learning model, the actual processing time of a job is affected by the sum of actual processing times of previous jobs and by a job-dependent truncation parameter. We show that the single machine problems to minimize makespan and to minimize the sum of weighted completion times are both at least ordinary NP-hard and the single machine problem to minimize maximum lateness is strongly NP-hard. We then show polynomial solvable cases and approximation algorithms for these problems. Computational experiments are also conducted to show the effectiveness of our approximation algorithms.

     

Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects

In this paper, we propose a new learning effect model in which the actual job processing time is a general function of the normal processing time of jobs already processed and its scheduled position. This model has the advantage that different learning curves can be constructed easily, such as the plateau function. It is found that most of the models in the literature are special cases of our proposed model. The optimal sequences for some single-machine problems are then provided.     

Single machine scheduling with general positional deterioration and rate-modifying maintenance

We present polynomial-time algorithms for single machine problems with generalized positional deterioration effects and machine maintenance. The decisions should be taken regarding possible sequences of jobs and on the number of maintenance activities to be included into a schedule in order to minimize the overall makespan. We deal with general non-decreasing functions to represent deterioration rates of job processing times. Another novel extension of existing models is our assumption that a maintenance activity does not necessarily fully restore the machine to its original perfect state. In the resulting schedules, the jobs are split into groups, a particular group to be sequenced after a particular maintenance period, and the actual processing time of a job is affected by the group that job is placed into and its position within the group.     

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

In this paper, we consider the single-machine scheduling problem with production and rejection costs to minimize the maximum earliness. If a job is accepted, then this job must be processed on the machine and a corresponding production cost needs be paid. If the job is rejected, then a corresponding rejection cost has to be paid. The objective is to minimize the sum of the maximum earliness of the accepted jobs, the total production cost of the accepted jobs and the total rejection cost of the rejected jobs. We show that this problem is equivalent to a single-machine scheduling problem to minimize the maximum earliness with two distinct rejection modes. In the latter problem, rejection cost might be negative in the rejection-award mode which is different from the traditional rejection-penalty mode in the previous literatures. We show that both of two problems are NP-hard in the ordinary sense and then provide two pseudo-polynomial-time algorithms to solve them. Finally, we also show that three special cases can be solved in polynomial time.     

MINIMIZING ABSOLUTE AND SQUARED DEVIATION OF COMPLETION TIMES FROM DUE DATES

This is a study of a single-machine scheduling problem with the objective of minimizing the sum of a function of earliness and tardiness called the earliness and tardiness (ET) problem. I will show that if priority weights of jobs are proportional to their processing times, and if earliness and tardiness cost functions are linear, the problem will be equivalent to the total weighted tardiness problem. This proves that the et problem is np -hard. In addition, I present a heuristic algorithm with worst case bound for the et problem based on the equivalence relation between the two. When earliness and tardiness cost functions are quadratic, I consider the problem for a common due date for all jobs and for different job due dates. In general, the et problem with quadratic earliness and tardiness cost functions and all job weights equal to one is np -hard. I show that in many cases, when weights of jobs are proportional to their processing times, the problem can be solved efficiently. In the published results on the et problem with quadratic earliness and tardiness cost functions other researchers have assumed a zero starting time for the schedule. I discuss the advantages of a nonzero starting time for the schedule.     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

Flow shop scheduling with deteriorating jobs under dominating machines

This paper addresses no-wait or no-idle flow shop scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting time. A simple linear deterioration function is assumed and some dominating relationships between machines can be satisfied. It is shown that for the problems to minimize makespan or weighted sum of completion time, polynomial algorithms still exist, although these problems are more complicated than the classical ones. When the objective is to minimize maximum lateness or maximum tardiness, the solutions of a classical version may not hold.     

Single machine scheduling problems with subcontracting options

In this paper, we study a scheduling model as follows: there are n jobs which can be processed in house on a single machine or subcontracted to a subcontractor. If a job is subcontracted, its processing cost is different from the in-house cost and its delivery lead time is a stepwise function of the total processing time of outsourced jobs. Two objective functions are studied (1) to minimize the weighted sum of the maximal completion time and the total processing cost and (2) to minimize the weighted sum of the number of tardy jobs and the total processing cost. For the first problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm. For the second problem, we prove that it is NP-hard and get a pseudo-polynomial time algorithm for a special case.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

Heuristic Estimation of the Efficient Frontier for a Bi-Criteria Scheduling Problem

We examine a single-machine scheduling problem where the objective is to minimize the mean and the variance of the job completion times simultaneously. We seek to identify the efficient frontier which is obtained by parametrically solving a weighted combination of the two criteria. The identification of the true efficient frontier for this problem is notoriously difficult. To estimate the frontier, we propose a heuristic procedure which is quite general and can be applied to other bi-criteria problems as well. It involves repeated applications of a relatively new technique called beam search in an adaptive manner. To evaluate the proposed procedure, we introduce two measures of performance and conduct a computational study. The results of the study indicate that the procedure is highly effective.     

On the Robust Single Machine Scheduling Problem

The single machine scheduling problem with sum of completion times criterion (SS) can be solved easily by the Shortest Processing Time (SPT) rule. In the case of significant uncertainty of the processing times, a robustness approach is appropriate. In this paper, we show that the robust version of the (SS) problem is NP-complete even for very restricted cases. We present an algorithm for finding optimal solutions for the robust (SS) problem using dynamic programming. We also provide two polynomial time heuristics and demonstrate their effectiveness.     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

Synchronous flow shop problems: How much can we gain by leaving machines idle?

In synchronous production lines it may be beneficial to leave machines idle instead of processing the next job immediately. In this paper, the effects of inserting voluntary idle times are discussed in more detail for different objective functions (minimization of makespan, total completion time, maximum lateness). Besides deriving theoretical bounds on how much can be gained by inserting idle times, an extensive computational study is conducted to empirically examine the actual improvements. For this, exact algorithms and heuristics capable of incorporating voluntary idle times are proposed to find (near-) optimal schedules. It can be seen that the potential gain is very large in theory, while the empirical results indicate that in general only small improvements are achievable in practice.     

A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling

In the multiprocessor scheduling problem to minimize the total job completion time, an optimal schedule can be obtained by the shortest processing time rule and the completion time of each job in the schedule can be used as a guarantee for scheduling revenue. However, in practice, some jobs will not arrive at the beginning of the schedule but are delayed and their delayed arrival times are given to the decision-maker for possible rescheduling. The decision-maker can choose to reject some jobs in order to minimize the total operational cost that includes three cost components: the total rejection cost of the rejected jobs, the total completion time of the accepted jobs, and the penalty on the maximum tardiness for the accepted jobs, for which their completion times in the planned schedule are their virtual due dates. This novel rescheduling problem generalizes several classic NP-hard scheduling problems. We first design a pseudo-polynomial time dynamic programming exact algorithm and then, when the tardiness can be unbounded, we develop it into a fully polynomial time approximation scheme. The dynamic programming exact algorithm has a space complexity too high for truthful implementation; we propose an alternative to integrate the enumeration and the dynamic programming recurrences, followed by a depth-first-search walk in the reschedule space. We implemented the alternative exact algorithm in C and conducted numerical experiments to demonstrate its promising performance.

     

Semi-online scheduling with “end of sequence” information

We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem. The authors would like to dedicate this paper to the memory of our colleague and friend Yong He who passed away in August 2005 after struggling with illness. D. Ye: Research was supported in part by NSFC (10601048).     

Resource constrained scheduling with general truncated job-dependent learning effect

Scheduling with general truncated job-dependent learning effect and resource-dependent processing times is studied on a single machine. It is assumed that the job processing time is a function of the amount of resource allocated to the job, the general job-dependent learning effect and the job-dependent control parameter. For each version of the problem that differs in terms of the objective functions and the processing time functions, the optimal resource allocation is provided. Polynomial time algorithms are also developed to find the optimal schedule of several versions of the problem.     

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

We study a single-machine scheduling model combining two competing agents and due-date assignment. The basic setting involves two agents who need to process their own sets of jobs, and compete on the use of a common processor. Our goal is to find the joint schedule that minimizes the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. The scheduling measure considered in this paper is minimum total (earliness, tardiness and due-date) cost, based on common flow allowance, i.e., due-dates are defined as linear functions of the job processing times. We introduce a simple polynomial time solution for this problem (linear in the number of jobs), as well as to its extension to a multi-agent setting. We further extend the model to that of a due-window assignment based on common flow allowance.     

Semi-online scheduling for jobs with release times

In this paper we consider three semi-online scheduling problems for jobs with release times on m identical parallel machines. The worst case performance ratios of the LS algorithm are analyzed. The objective function is to minimize the maximum completion time of all machines, i.e. the makespan. If the job list has a non-decreasing release times, then $2-\frac{1}{m}$ is the tight bound of the worst case performance ratio of the LS algorithm. If the job list has non-increasing processing times, we show that $2-\frac{1}{2m}$ is an upper bound of the worst case performance ratio of the LS algorithm. Furthermore if the job list has non-decreasing release times and the job list has non-increasing processing times we prove that the LS algorithm has worst case performance ratio not greater than $\frac{3}{2} -\frac{1}{2m}$ .     

Scheduling two job families on a single machine with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a single machine. A setup time is needed for a job if it is the first job to be processed on the machine or its processing on the machine follows a job that belongs to another family. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The aim is to find a schedule for all the jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent being bounded by a fixed value \(Q\). Polynomial-time and pseudo-polynomial-time algorithms are designed to solve the problem involving various combinations of regular scheduling objective functions.