IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i5p699-d1347445.html
   My bibliography  Save this article

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. 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.
    2. 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).
    3. 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.
    4. 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.
    5. 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.
    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. 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.
    2. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    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. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Reijnierse, Hans & Borm, Peter & Quant, Marieke & Meertens, Marc, 2010. "Processing games with restricted capacities," European Journal of Operational Research, Elsevier, vol. 202(3), pages 773-780, May.
    14. 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.
    15. Borm, Peter & Fiestras-Janeiro, Gloria & Hamers, Herbert & Sanchez, Estela & Voorneveld, Mark, 2002. "On the convexity of games corresponding to sequencing situations with due dates," European Journal of Operational Research, Elsevier, vol. 136(3), pages 616-634, February.
    16. 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.
    17. 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.
    18. Hanane Krim & Rachid Benmansour & David Duvivier & Daoud Aït-Kadi & Said Hanafi, 2020. "Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance," Computational Optimization and Applications, Springer, vol. 75(1), pages 291-320, January.
    19. M. Musegaas & P. E. M. Borm & M. Quant, 2018. "On the convexity of step out–step in sequencing games," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(1), pages 68-109, April.
    20. Daniel Kowalczyk & Roel Leus, 2018. "A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 768-782, November.

    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.