2022/03/18 by Nodari Vakhania, Frank Werner, Vakhania, Nodari +3
Computer Science · Engineering · #90B35 #Data Structures and Algorithms (cs.DS) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #FOS: Mathematics #G.2 #Optimization and Control (math.OC) #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2203.09800
openalex publication_date 2022/03/18 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
The problem of scheduling non-simultaneously released jobs with due dates on\na single machine with the objective to minimize the maximum job lateness is\nknown to be strongly NP-hard. Here we consider an extended model in which the\ncompression of the job processing times is allowed. The compression is\naccomplished at the cost of involving additional emerging resources, whose use,\nhowever, yields some cost. With a given upper limit U on the total allowable\ncost, one wishes to minimize the maximum job lateness. It is clear that, by\nusing the available resources, some jobs may complete earlier and the objective\nfunction value may respectively be decreased. As we show here, for minimizing\nthe maximum job lateness, by shortening the processing time of some specially\ndetermined jobs, the objective value can be decreased. Although the generalized\nproblem is harder than the generic non-compressible version, given a\n``sufficient amount'' of additional resources, we can solve the problem\noptimally. We determine the compression rate for some specific jobs and develop\nan algorithm that obtains an optimal solution. Such an approach can be\nbeneficial in practice since the manufacturer can be provided with an\ninformation about the required amount of additional resources in order to solve\nthe problem optimally. In case the amount of the available additional resources\nis less than used in the above solution, i.e., it is not feasible, it is\ntransformed to a tight minimal feasible solution.\n