Fast solution of single-machine scheduling problem with embedded jobs

作     者：Vakhania, Nodari 

作者机构：UAEMor Ctr Invest Ciencias Cuernavaca Morelos Mexico 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第782卷第0期

页      面：91-106页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：The author is grateful to Luca Vakhania for his kind help in the elaboration of the figures using Xfig graphical interface 

主　　题：Polynomial-time algorithm Single-machine scheduling Release time Due date Lateness Time complexity 

摘      要：We present a fast polynomial-time algorithm for single-machine scheduling problem with release times (r(j)), processing times (p(j)) and due dates (d(j)) with the objective to minimize the maximum job lateness. The general setting is strongly NP-hard. We expose a particular embedded structure that typically possess a subset of jobs in an instance of the problem. We establish useful properties of the problem instances that tolerate this structure, i.e., in such an instance no subset of embedded jobs overlaps in time with the jobs that do not belong to that subset. Relying on these properties, our algorithm finds an optimal solution for the corresponding class of problem instances. Whether a given problem instance is tolerant of the revealed embedded structure becomes known during the execution of the algorithm. Nevertheless, some sufficient conditions in terms of job parameters can a priori be given. One such a condition is that for any pair of jobs j and i with r(i) r(j) and d(i) = r(j) + p(j), then d(i) = d(j). As we show, our setting remains powerful enough to model important real-life applications. (C) 2019 Elsevier B.V. All rights reserved.