Approximation of the Objective Function of Single-Machine Scheduling Problem

Alexander Lazarev, Nikolay Pravdivets () and Egor Barashov
Additional contact information
Alexander Lazarev: V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia
Nikolay Pravdivets: V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia
Egor Barashov: V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia

Mathematics, 2024, vol. 12, issue 5, 1-16

Abstract: The problem of the approximation of the coefficients of the objective function of a scheduling problem for a single machine is considered. It is necessary to minimize the total weighted completion times of jobs with unknown weight coefficients when a set of problem instances with known optimal schedules is given. It is shown that the approximation problem can be reduced to finding a solution to a system of linear inequalities for weight coefficients. For the case of simultaneous job release times, a method for solving the corresponding system of inequalities has been developed. Based on it, a polynomial algorithm for finding values of weight coefficients that satisfy the given optimal schedules was constructed. The complexity of the algorithm is O ( n 2 ( N + n ) ) operations, where n is the number of jobs and N is the number of given instances with known optimal schedules. The accuracy of the algorithm is estimated by experimentally measuring the function ε ( N , n ) = 1 n ∑ j = 1 n ∣ w j − w j 0 ∣ w j 0 , which is an indicator of the average modulus of the relative deviation of the found values w j from the true values w j 0 . An analysis of the results shows a high correlation between the dependence ε ( N , n ) and a function of the form α ( n ) / N , where α ( n ) is a decreasing function of n .

Keywords: scheduling theory; single machine scheduling; total weighted completion times; approximation (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/5/699/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/5/699/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:5:p:699-:d:1347445

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().