Search

We consider a basic preemptive scheduling problem where n non-simultaneously released jobs are to be processed by m unrelated parallel machines so as to minimize maximum job completion time. An optimal LP-solution has been used to construct an optimal preemptive schedule for simultaneously released jobs in time O(n³). We propose fast O(m) time algorithm that finds an optimal schedule in case the above LP-solution possesses "small enough" number of non-zero elements. We propose another linear program for non-simultaneously released jobs and show how an optimal schedule can be constructed also in time O(m) from the optimal solution to that linear program. Based on another stronger linear program formulation, we extend the earlier known schedule construction procedure for non-simultaneously released jobs. The procedure is important, in particular, because there may exist no optimal schedule that agrees with an optimal LP-solution. An optimal LPsolution imposes a number of preemptions, and additional preemptions may occur during the schedule construction process, a job might be forced to be split on the same machine. We show that if no job split is allowed, even a restricted version of the problem on three unrelated machines is NP-hard. As a result, we obtain that, given an optimal LP-solution, it is NP-hard to find an optimal schedule that agrees with that LP-solution. As another side result, we obtain that it is NP-hard to find an optimal schedule with at most m - 1 preemptions. [ABSTRACT FROM AUTHOR]

We study a single-machine scheduling problem with two allowable job release and delivery times. This special case of a strongly NP-hard single-machine scheduling problem with an arbitrary number of job release and delivery times and with the objective to minimize the maximum job completion time remains NP-hard. Nevertheless, it is more transparent and accessible than the general version. Hence, it permitted us to establish some nice properties that yielded simple and efficient solution methods. On the one hand, the restricted setting is useful by its own right since it fits some real-life applications. On the other hand, the presented case study is helpful in the solution of a more general setting with a constant number of job release and delivery times. In particular, the optimality conditions and the heuristics methods that we propose here for the restricted setting might be generalized to the extended setting. The established optimality criteria are explicit conditions under which the restricted problem can be solved optimally in time O (n log n) . The extensive computational study showed that at least one of these conditions is satisfied for practically all the randomly generated 50 million problem instances while applying our heuristics to these instances. We report a favorable practical performance of our polynomial-time subroutine that invokes our five heuristics and verifies the proposed optimality conditions consecutively. These conditions were verified for the solutions delivered by the five heuristics individually and in a combined fashion as four pairs of heuristics and as all the five heuristics together. Fifty million problem instances were randomly generated using uniform distribution for each of these ten combinations. For the 50 million instances generated for the last (overall) combination, the schedule created by at least one of the heuristics has satisfied at least one of our optimality conditions (so all these problem instances were solved optimally). We also addressed the (theoretical) possibility that none of our conditions is satisfied, and showed how a known dynamic programming algorithm for SUBSET SUM problem can be used for the solution of the scheduling problem in pseudo-polynomial time. For a considerable part of the tested instances, one of the five scheduling heuristics has solved optimally also SUBSET SUM problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines. This problem is a generalisation of the much more common problem of scheduling equal-length jobs on identical machines. Such a situation may occur in the production of two different types of products. First, we show that an earlier open problem of scheduling jobs with two possible processing times and on unrelated machines with the objective to minimise the makespan can be polynomially solved by an algorithm consisting of two phases. A slight modification of this algorithm yields an absolute worst-case error of for the case of two arbitrary processing times and ,. Thus, for practical problems of a large size with two types of products and two possible processing times, the approximation algorithm generates schedules very close to an optimal one. [ABSTRACT FROM AUTHOR]

Some special cases of single-machine problems is considered. In these cases there are many optimal solutions. It is given the formulas of quantity of optimal solutions and calculated the probability of the event that an arbitrary schedule is optimal; the sufficient conditions to increase the value of this probability is given and the corresponding optimal full completion time is calculated. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling jobs with release times and tails on a single machine with the objective to minimize the makespan. This problem is strongly NP-hard, however it is known to be polynomially solvable if all jobs have equal processing time P. We generalize this result and suggest an O( n2 log nlog P) algorithm for the case when the processing times of some jobs are restricted to either P or 2 P. [ABSTRACT FROM AUTHOR]

The problem of sequencing n equal-length jobs on m identical machines to minimize the maximal job completion time subject to release and delivery times is considered. An algorithm is proposed which improves the running time of previously known algorithms. The time complexity of the algorithm is O(qmaxmnlogn+O(mκn)), where qmax is the maximal job delivery time and κ is a parameter which is known only after the termination of the algorithm; in practice, κ turns out to be a small positive integer. [Copyright &y& Elsevier]

We consider the problem of scheduling n jobs with identical processing times and given release as well as delivery times on m uniform machines. The goal is to minimize the makespan, i.e., the maximum full completion time of any job. This problem is well-known to have an open complexity status even if the number of jobs is fixed. We present a polynomial-time algorithm for the problem which is based on the earlier introduced algorithmic framework blesscmore ("branch less and cut more"). We extend the analysis of the so-called behavior alternatives developed earlier for the version of the problem with identical parallel machines and show how the earlier used technique for identical machines can be extended to the uniform machine environment if a special condition on the job parameters is imposed. The time complexity of the proposed algorithm is O (γ m 2 n log n) , where γ can be either n or the maximum job delivery time q max . This complexity can even be reduced further by using a smaller number κ < n in the estimation describing the number of jobs of particular types. However, this number κ becomes only known when the algorithm has terminated. [ABSTRACT FROM AUTHOR]

Scheduling jobs with release and due dates on a single machine is a classical strongly NP-hard combination optimization problem. It has not only immediate real-life applications but also it is effectively used for the solution of more complex multiprocessor and shop scheduling problems. Here, we propose a general method that can be applied to the scheduling problems with job release times and due-dates. Based on this method, we carry out a detailed study of the single-machine scheduling problem, disclosing its useful structural properties. These properties give us more insight into the complex nature of the problem and its bottleneck feature that makes it intractable. This method also helps us to expose explicit conditions when the problem can be solved in polynomial time. In particular, we establish the complexity status of the special case of the problem in which job processing times are mutually divisible by constructing a polynomial-time algorithm that solves this setting. Apparently, this setting is a maximal polynomially solvable special case of the single-machine scheduling problem with non-arbitrary job processing times. [ABSTRACT FROM AUTHOR]

We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework. [ABSTRACT FROM AUTHOR]

Motivated by the conjecture that an interaction between scheduling and pre-scheduling phases in production planning may give certain benefits, we conduct a detailed study of the optimality conditions and dominance relations for a strongly NP-hard single-machine scheduling model when jobs have release and due-dates and the objective is to minimize maximum job lateness. By exploring the inherent structure of the problem, we establish the optimality conditions when the problem can be efficiently solved. We come to an NP-hard special case of the problem with only two possible job release times, that as we show allows stricter dominance rules and optimality conditions verifiable in polynomial time. The established properties give a potential of a beneficial interaction between scheduling and pre-scheduling phases in production planning, and also provide basic theoretical background for the construction of efficient heuristic and implicit enumerative algorithms. [ABSTRACT FROM AUTHOR]

The following scheduling problem is studied: We are given a set of tasks with release times, deadlines, and profit rates. The objective is to determine a 1-processor preemptive schedule of the given tasks that maximizes the overall profit. In the standard model, each completed task brings profit, while non-completed tasks do not. In the metered model, a task brings profit proportional to the execution time even if not completed. For the metered task model, we present an efficient offline algorithm and improve both the lower and upper bounds on the competitive ratio of online algorithms. Furthermore, we prove three lower bound results concerning resource augmentation in both models. [Copyright &y& Elsevier]