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.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

Single machine scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many practical cases, one may wish to reject the processing of some jobs in the shop, which results in a rejection cost. A solution for a scheduling problem with rejection is given by partitioning the jobs into a set of accepted and a set of rejected jobs, and by scheduling the set of accepted jobs among the machines. The quality of a solution is measured by two criteria: a scheduling criterion, F1, which is dependent on the completion times of the accepted jobs, and the total rejection cost, F2. Problems of scheduling with rejection have been previously studied, but usually within a narrow framework—focusing on one scheduling criterion at a time. This paper provides a robust unified bicriteria analysis of a large set of single machine problems sharing a common property, namely, all problems can be represented by or reduced to a scheduling problem with a scheduling criterion which includes positional penalties. Among these problems are the minimization of the makespan, the sum of completion times, the sum and variation of completion times, and the total earliness plus tardiness costs where the due dates are assignable. Four different problem variations for dealing with the two criteria are studied. The variation of minimizing F1+F2 is shown to be solvable in polynomial time, while all other three variations are shown to be $\mathcal{NP}$ -hard. For those hard problems we provide a pseudo polynomial time algorithm. An FPTAS for obtaining an approximate efficient schedule is provided as well. In addition, we present some interesting special cases which are solvable in polynomial time.     

Semi-online scheduling on two identical machines with rejection

In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. In the first problem one can reassign several scheduled jobs in rejection tache, in the second a buffer with length k is available in rejection tache. Two optimal algorithms both with competitive ratio $\frac{3}{2}$ are presented.     

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.

     

Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties

In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.

     

New results on two-machine flow-shop scheduling with rejection

In this paper, we consider the off-line and on-line two-machine flow-shop scheduling problems with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. For the off-line version, Shabtay and Gasper (Comput Oper Res 39:1087–1096, 2012) showed that this problem is NP-hard and then provided a pseudo-polynomial-time algorithm, two 2-approximation algorithms and a fully polynomial-time approximation scheme. We further study some special cases in this paper. We show that this problem is still NP-hard even when all jobs have the same processing time on one of the machines or all jobs have the same rejection penalty. Furthermore, we also showed that this problem can be solved in polynomialtime algorithm when all jobs satisfy the agreeable condition on their processing times and rejection penalties. For the on-line version without rejection, Chen and Woeginger [in: Du DZ, Pardalos PM (eds.) Minimax and Applications, 1995] showed that the competitive ratio of any determined on-line algorithm is at least 2. We further show that the competitive ratio of any determined on-line algorithm is at least 2 even when all jobs have the same processing time on the first machine. Finally, for the on-line version with rejection, we present a class of on-line algorithms with the best-possible competitive ratio 2.     

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.     

Online scheduling with rejection and reordering: exact algorithms for unit size jobs

We study an online scheduling problem with rejection on \(m\ge 2\) identical machines, in which we deal with unit size jobs. Each arriving job has a rejection value (a rejection cost or penalty for minimization problems, and a rejection profit for maximization problems) associated with it. A buffer of size \(K\) is available to store \(K\) jobs. A job which is not stored in the buffer must be either assigned to a machine or rejected. Upon the arrival of a new job, the job can be stored in the buffer if there is a free slot (possibly created by evicting other jobs and assigning or rejecting every evicted job). At termination, the buffer must be emptied. We study four variants of the problem, as follows. We study the makespan minimization problem, where the goal is to minimize the sum of the makespan and the penalty of rejected jobs, and the \(\ell _p\) norm minimization problem, where the goal is to minimize the sum of the \(\ell _p\) norm of the vector of machine completion times and the penalty of rejected jobs. We also study two maximization problems, where the goal in the first version is to maximize the sum of the minimum machine load (the cover value of the machines) and the total rejection profit, and in the second version the goal is to maximize a function of the machine completion times (which measures the balance of machine loads) and the total rejection profit. We show that an optimal solution (an exact solution for the offline problem) can always be obtained in this environment, and determine the required buffer size. Specifically, for all four variants we present optimal algorithms with \(K=m-1\) and prove that in each case, using a buffer of size at most \(m-2\) does not allow the design of an optimal algorithm, which makes our algorithms optimal in this respect as well. The lower bounds hold even for the special case where the rejection value is equal for all input jobs.     

Scheduling with release times and rejection on two parallel machines

In this paper we study scheduling with release times and job rejection on two parallel machines. In our scheduling model each job is either accepted and then processed by one of the two machines at or after its release time, or it is rejected and then a rejection penalty is paid. The objective is to minimize the makespan of the accepted job plus the total penalty of all rejected jobs. The scheduling problem is NP-hard in the ordinary sense. In this paper, we develop a \(1.5+\epsilon \)-approximation algorithm for the problem, where \(\epsilon \) is any given small positive constant.     

Online integrated production–distribution scheduling problems without preemption

We study an integrated production–distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given.     

Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence

In this paper, we introduce the concept of “workload fence" into online machine rental and machine scheduling problems. With the knowledge of workload fence, online algorithms acquire the information of a finite number of first released jobs in advance. The concept originates from the frozen time fence in the domain of master scheduling in materials management. The total processing time of the jobs foreseen, corresponding to a finite number of jobs, is called workload fence, which is irrelevant to the job sequence. The remaining jobs in the sequence, however, can only become known on their arrival. This work aims to reveal whether the knowledge of workload fence helps to boost the competitive performance of deterministic online algorithms. For the online machine rental problem, we prove that the competitiveness of online algorithms can be improved with a sufficiently large workload fence. We further propose a best online algorithm for the corresponding scenario. For online parallel machine scheduling with workload fence, we give a positive answer to the above question for the case where the workload fence is equal to the length of the longest job. We also show that the competitiveness of online algorithms may not be improved even with a workload fence strictly larger than the largest length of a job. The results help one manager to make a better decision regarding the tradeoff between the performance improvement of online algorithms and the cost caused to acquire the knowledge of workload fence.

     

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.     

Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.     

AN EVALUATION OF ORDER RELEASE MECHANISMS IN A JOB-SHOP ENVIRONMENT

Controlling the flow of material on the shop floor involves releasing and dispatching jobs to meet customer due-date requirements while attempting to keep operating costs low. This report presents an evaluation of five releasing mechanisms and four dispatching rules under various levels of aggregate due-date tightness, shop cost structure, and machine utilization using simulation. The performance criteria of total shop cost, jobs on shop floor, deviation from due dates, and job queue time are collected to demonstrate the interactive nature of releasing and dispatching on shop performance.     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.     

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.     

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.     

Online lazy bureaucrat scheduling with a machine deadline

The lazy bureaucrat scheduling problem was first introduced by Arkin et al. (Inf Comput 184:129–146, 2003). Since then, a number of variants have been addressed. However, very little is known on the online version. In this note we focus on the scenario of online scheduling, in which the jobs arrive over time. The bureaucrat (machine) has a working time interval. Namely, he has a deadline by which all scheduled jobs must be completed. A decision is only based on released jobs without any information on the future. We consider two objective functions of [min-makespan] and [min-time-spent]. Both admit best possible online algorithms with competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\).