IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i5p699-d1347445.html

Approximation of the Objective Function of Single-Machine Scheduling Problem

Author

Listed:
  • 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
    Department of Mathematics, Faculty of Economic Sciences, HSE University, 11 Pokrovsky Boulevard, 109028 Moscow, Russia)

  • Egor Barashov

    (V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya Street, 117997 Moscow, Russia)

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 .

Suggested Citation

  • Alexander Lazarev & Nikolay Pravdivets & Egor Barashov, 2024. "Approximation of the Objective Function of Single-Machine Scheduling Problem," Mathematics, MDPI, vol. 12(5), pages 1-16, February.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:5:p:699-:d:1347445
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/5/699/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/5/699/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Zhao, Xian & Liu, Haoran & Wu, Yaguang & Qiu, Qingan, 2023. "Joint optimization of mission abort and system structure considering dynamic tasks," Reliability Engineering and System Safety, Elsevier, vol. 234(C).
    2. Mosheiov, Gur & Oron, Daniel & Shabtay, Dvir, 2021. "Minimizing total late work on a single machine with generalized due-dates," European Journal of Operational Research, Elsevier, vol. 293(3), pages 837-846.
    3. Behdin Vahedi-Nouri & Reza Tavakkoli-Moghaddam & Zdeněk Hanzálek & Alexandre Dolgui, 2024. "Production scheduling in a reconfigurable manufacturing system benefiting from human-robot collaboration," International Journal of Production Research, Taylor & Francis Journals, vol. 62(3), pages 767-783, February.
    4. K. Tanaka & M. Vlach, 1999. "Minimizing maximum absolute lateness and range of lateness under generalizeddue dates on a single machine," Annals of Operations Research, Springer, vol. 86(0), pages 507-526, January.
    5. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, March.
    6. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Gawiejnowicz, Stanisław, 2026. "Theory and methodology of time-dependent scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 329(3), pages 719-746.
    2. Enrique Gerstl & Gur Mosheiov, 2020. "Single machine scheduling to maximize the number of on-time jobs with generalized due-dates," Journal of Scheduling, Springer, vol. 23(3), pages 289-299, June.
    3. José R. Correa & Maurice Queyranne, 2012. "Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 384-395, August.
    4. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    5. Jiang, Yiwei & Wu, Mengjing & Chen, Xin & Dong, Jianming & Cheng, T.C.E. & Blazewicz, Jacek & Ji, Min, 2024. "Online early work scheduling on parallel machines," European Journal of Operational Research, Elsevier, vol. 315(3), pages 855-862.
    6. Baruch Mor & Gur Mosheiov & Dvir Shabtay, 2021. "Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates," Journal of Scheduling, Springer, vol. 24(6), pages 553-567, December.
    7. Qiuping Yu & Gad Allon & Achal Bassamboo & Seyed Iravani, 2018. "Managing Customer Expectations and Priorities in Service Systems," Management Science, INFORMS, vol. 64(8), pages 3942-3970, August.
    8. Lili Liu & Guochun Tang & Baoqiang Fan & Xingpeng Wang, 2015. "Two-person cooperative games on scheduling problems in outpatient pharmacy dispensing process," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 938-948, November.
    9. van Beek, Andries & Malmberg, Benjamin & Borm, Peter & Quant, Marieke & Schouten, Jop, 2021. "Cooperation and Competition in Linear Production and Sequencing Processes," Discussion Paper 2021-011, Tilburg University, Center for Economic Research.
    10. Gabriel Zayas‐Cabán & Emmett J. Lodree & David L. Kaufman, 2020. "Optimal Control of Parallel Queues for Managing Volunteer Convergence," Production and Operations Management, Production and Operations Management Society, vol. 29(10), pages 2268-2288, October.
    11. Byung-Cheon Choi & Myoung-Ju Park & Kyung Min Kim, 2025. "Two-machine permutation flow shop scheduling with generalized due dates to minimize total late work," Journal of Scheduling, Springer, vol. 28(6), pages 563-576, December.
    12. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    13. Nicholas G. Hall & Marc E. Posner & Chris N. Potts, 2021. "Online production planning to maximize the number of on-time orders," Annals of Operations Research, Springer, vol. 298(1), pages 249-269, March.
    14. Bachtenkirch, David & Bock, Stefan, 2022. "Finding efficient make-to-order production and batch delivery schedules," European Journal of Operational Research, Elsevier, vol. 297(1), pages 133-152.
    15. Hermelin, Danny & Molter, Hendrik & Niedermeier, Rolf & Pinedo, Michael & Shabtay, Dvir, 2025. "Fairness in repetitive scheduling," European Journal of Operational Research, Elsevier, vol. 323(3), pages 724-738.
    16. Zhao, Xian & Wang, Xinlei & Dai, Ying & Qiu, Qingan, 2024. "Joint optimization of loading, mission abort and rescue site selection policies for UAV," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    17. Levitin, Gregory & Xing, Liudong & Dai, Yuanshun, 2024. "Optimal system loading and aborting in additive multi-attempt missions," Reliability Engineering and System Safety, Elsevier, vol. 251(C).
    18. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    19. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    20. T.C. Edwin Cheng & Qingqin Nong & Chi To Ng, 2011. "Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(8), pages 763-770, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:5:p:699-:d:1347445. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.