Bi-criteria and tri-criteria analysis to minimize maximum lateness makespan and resource consumption for scheduling a single machine

We analyze two single machine scheduling problems for the case where job processing times are controllable, by allocating continuous and non-renewable resources to the processing operations. The first problem to analyze is constructing the trade-off curve between maximum lateness and total resource consumption; an O(n ²) computational time optimization algorithm was constructed to solve this problem. This algorithm was extended to solve the second problem, which is to construct the trade-off surface between maximum lateness, makespan, and total resource consumption. As part of this algorithm we identify a plane in the 3D field that is formed by the three criteria, which is parallel only to the maximum lateness, and calculate the optimal makespan and total resource consumption as functions of points on this plane. The extended algorithm keeps the same complexity of O(n ²) time. Both algorithms are very robust as they solve the problem for a very large set of resource consumption functions which has to follow only some mild (and commonly acceptable) conditions. Moreover, as far as we know, this is the first research of its kind in the field of multi-objective scheduling to present an algorithm that constructs a 3D trade-off surface.     

Single-machine batch delivery scheduling with an assignable common due date and controllable processing times

We consider single-machine batch delivery scheduling with an assignable common due date and controllable processing times, which vary as a convex function of the amounts of a continuously divisible common resource allocated to individual jobs. Finished jobs are delivered in batches and there is no capacity limit on each delivery batch. We first provide an O(n⁵) dynamic programming algorithm to find the optimal job sequence, the partition of the job sequence into batches, the assigned common due date, and the resource allocation that minimize a cost function based on earliness, tardiness, job holding, due date assignment, batch delivery, and resource consumption. We show that a special case of the problem can be solved by a lower-order polynomial algorithm. We then study the problem of finding the optimal solution to minimize the total cost of earliness, tardiness, job holding, and due date assignment, subject to limited resource availability, and develop an O(nlog n) algorithm to solve it.     

Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation

In many resource allocation problems in physical or economic systems, a linear resource consumption function is commonly considered, and job processing times are assumed to be fixed parameters. However, the former assumption fails to reflect the law of diminishing returns, and the latter may be controlled by changing the allocation of resources to jobs. Motivated by these observations, we provide a unified model for solving single-machine scheduling problems in which each job's processing time is a function of its starting time and convex resource allocation. The objective is to find the optimal sequence of jobs subject to a limited resource consumption. We first show how this unified model can be useful in solving scheduling problems under due date assignment considerations. We analyze the problem with four different due date assignment methods, and our objective function includes costs for earliness, tardiness and due date assignments. We also consider scheduling problems without involving due date assignment decisions. The objective function is to minimize the makespan, total completion time, total absolute variation in completion times, and total absolute variation in waiting times. We show that several existing well-known problems can be reduced to a special case of our unified model and solved in O(nlogn) time.     

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.     

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.     

An analysis of service schedules for the mobile k-server problem

In the mobile k-server problem, servers with fixed home locations travel to locations of requests to provide service and then return to their home locations. Given the home locations of the k-servers, the service times, release times and locations of the n requests, we seek to determine a service schedule so that the total waiting time of all requests is minimized. In this paper, we exploit the strong connection between the mobile k-server problem and job scheduling. We present optimal algorithms for a few special cases of the problem and provide worst-case performance analysis of some heuristics for the general case. For the special cases it is possible to rank order competing sets of home locations with respect to total (or average) waiting time.     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

Resource optimal control in some single-machine scheduling problems

We consider a problem to schedule a set of jobs on a single machine under the constraint that the maximum job completion time does not exceed a given limit. Before a job is released for processing, it must undergo some preprocessing treatment which consumes resources. It is assumed that the release time of a job is a positive strictly decreasing continuous function of the amount of resources consumed. The objective is to minimize the total resource consumption. We show that ordering jobs in nonincreasing processing times yields an optimal solution. We then consider a bicriterion approach to the problem in which the maximum job completion time and the resource consumption are simultaneously minimized and present a polynomial time solution algorithm. Finally, we consider a related problem in which the job release times are given but the processing times are functions of the amount of resource consumed. We show that ordering jobs in nondecreasing release times gives an optimal solution and that the problem to minimize both the maximum completion time and resource consumption is polynomially solvable     

Path-distance heuristics for the Steiner problem in undirected networks

An integrative overview of the algorithmic characteristics of three well-known polynomialtime heuristics for the undirected Steiner minimum tree problem:shortest path heuristic (SPH),distance network heuristic (DNH), andaverage distance heuristic (ADH) is given. The performance of thesesingle-pass heuristics (and some variants) is compared and contrasted with several heuristics based onrepetitive applications of the SPH. It is shown that two of these repetitive SPH variants generate solutions that in general are better than solutions obtained by any single-pass heuristic. The worst-case time complexity of the two new variants isO(pn ³) andO(p ³ n ²), while the worst-case time complexity of the SPH, DNH, and ADH is respectivelyO(pn ²),O(m + n logn), andO(n ³) wherep is the number of vertices to be spanned,n is the total number of vertices, andm is the total number of edges. However, use of few simple tests is shown to provide large reductions of problem instances (both in terms of vertices and in term of edges). As a consequence, a substantial speed-up is obtained so that the repetitive variants are also competitive with respect to running times.     

Scheduling Partially Ordered Jobs Faster than 2 n

In a scheduling problem, denoted by 1|prec|∑C _i in the Graham notation, we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. 1|prec|∑C _i is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2 ⁿ n ^O(1) time, and whether there exists an algorithms solving 1|prec|∑C _i in O(c ⁿ ) time for some constant c<2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.     

Minimizing the maximal weighted lateness of delivering orders between two railroad stations

We consider the planning problem for freight transportation between two railroad stations. We are required to fulfill orders (transport cars by trains) that arrive at arbitrary time moments and have different value (weight). The speed of trains moving between stations may be different. We consider problem settings with both fixed and undefined departure times for the trains. For the problem with fixed train departure times we propose an algorithm for minimizing the weighted lateness of orders with time complexity O(qn ² log n) operations, where q is the number of trains and n is the number of orders. For the problem with undefined train departure and arrival times we construct a Pareto optimal set of schedules optimal with respect to criteria wL _max and C _max in O(n ² max{n log n, q log v}) operations, where v is the number of time windows during which the trains can depart. The proposed algorithm allows to minimize both weighted lateness wL _max and total time of fulfilling freight delivery orders C _max.     

Scheduling problems with two competing agents to minimized weighted earliness–tardiness

We study scheduling problems with two competing agents, sharing the same machines. All the jobs of both agents have identical processing times and a common due date. Each agent needs to process a set of jobs, and has his own objective function. The objective of the first agent is total weighted earliness–tardiness, whereas the objective of the second agent is maximum weighted deviation from the common due date. Our goal is to minimize the objective of the first agent, subject to an upper bound on the objective value of the second agent. We consider a single machine, and parallel (both identical and uniform) machine settings. An optimal solution in all cases is shown to be obtained in polynomial time by solving a number of linear assignment problems. We show that the running times of the single and the parallel identical machine algorithms are O(n^m+3), where n is the number of jobs and m is the number of machines. The algorithm for solving the problem on parallel uniform machine requires O(n^m+3m³) time, and under very reasonable assumptions on the machine speeds, is reduced to O(n^m+3). Since the number of machines is given, these running times are polynomial in the number of jobs.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the weighted sum of completion times. No polynomial 2-approximation algorithm for this problem has been previously known. We propose a 2-approximation algorithm with O(n²) time complexity where n is the number of jobs. We show that this bound is tight. The obtained result outperforms all the previous polynomial approximation algorithms for this problem.     

On the complexity of interval scheduling with a resource constraint

We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job j are: a fixed start time s_j, a fixed finish time f_j, and a resource requirement r_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, the problem is to decide whether a feasible schedule for all jobs exists or not.We discuss such a decision problem and prove that it is strongly NP-complete even when the number of resources are fixed to any value R≥2. Moreover, we suggest an implicit enumeration algorithm which has O(nlogn) time complexity in the number n of jobs when the number m of machines and the number R of resources per machine are fixed.The role of storage layout and preemption are also discussed.     

Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time

Zhao et al. (2009) [24] study the m identical parallel-machine scheduling problem with rate-modifying activities to minimize the total completion time. They show that the problem can be solved in O(n^2m+3) time. In this study we extend the scheduling environment to the unrelated parallel-machine setting and present a more efficient algorithm to solve the extended problem. For the cases where the rate-modifying rate is (i) larger than 0 and not larger than 1, and (ii) larger than 0, we show that the problem can be solved in O(n^m+3) and O(n^2m+2) time, respectively.     

A multi-dimensional indexing approach for timestamped event sequence matching

This paper addresses the problem of timestamped event sequence matching, a new type of similar sequence matching that retrieves the occurrences of interesting patterns from timestamped sequence databases. The sequential-scan-based method, the trie-based method, and the method based on the iso-depth index are well-known approaches to this problem. In this paper, we point out their shortcomings, and propose a new method that effectively overcomes these shortcomings. The proposed method employs an R^∗-tree, a widely accepted multi-dimensional index structure that efficiently supports timestamped event sequence matching. To build the R^∗-tree, this method extracts time windows from every item in a timestamped event sequence and represents them as rectangles in n-dimensional space by considering the first and last occurring times of each event type. Here, n is the total number of disparate event types that may occur in a target application. To resolve the dimensionality curse in the case when n is large, we suggest an algorithm for reducing the dimensionality by grouping the event types. Our sequence matching method based on the R^∗-tree performs with two steps. First, it efficiently identifies a small number of candidates by searching the R^∗-tree. Second, it picks out true answers from the set of candidates. We prove its robustness formally, and also show its effectiveness via extensive experiments.