زمانبندی با تاریخ انتشار قابل کنترل و زمان پردازش: به حداقل رساندن زمان اتمام کل

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n2) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.

This paper continues the study of the single machine problem with controllable processing times and release dates started in [3]. In both papers it is assumed that the job processing times and release dates may vary within certain limits. Compressing any of the two parameters incurs the compression cost that is represented by a linear function of the compression amounts. Such problems arise in manufacturing systems, supply chain scheduling, computing systems that support imprecise computations, computer networks, etc. (see [2], [3], [7], [10] and [11] for the examples and references). In [3] we study the problem of minimizing the makespan together with the compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n2) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times we suggest an O(n2) algorithm that constructs the breakpoints of the efficient frontier. The current paper focuses on the problem of minimizing the sum of the total completion time and the compression cost. We adapt the techniques developed in [3] and suggest a generalized algorithm that is applicable to the problem with single machine or parallel machines and to a range of problems with a common due date and controllable processing times. The main problem studied in this paper can be formulated as follows. Each job from the set N = {1, … , n} has to be processed on a single machine without preemption. Each job i ∈ N is characterized by the two parameters: release date ri and processing time pi each of which can vary within certain limits:

It should be noted that while the generalized version A′ of Algorithm A from [3] is more complicated, the parallel machine problem with FΣ objective function is polynomially solvable (see Section 4.1). However, a similar parallel machine problem with the makespan objective is NP-hard (see [3]). An interesting topic for further research is establishing the computational complexity of problem PΣ for arbitrary αi and βi = β. Observe that if the processing times are fixed, then the problem is equivalent to problem 1|d|∑(wiEi+Ti)1|d|∑(wiEi+Ti) of minimizing the weighted total earliness Ei = max{d − Ci, 0} and total tardiness Ti = max{Ci − d, 0} with unrestricted common due-date d. The complexity status of the latter problem is unknown.