iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/BF01680374
Optimal makespan schedule for three jobs on two machines | Mathematical Methods of Operations Research Skip to main content
Springer Nature Link
Log in

Optimal makespan schedule for three jobs on two machines

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

This paper deals with the problem of scheduling three jobs on two machines in order to minimize the makespan, when operation preemptions are forbidden and routes are fixed and may vary per job. It is shown that this problem can be solved by anO(r 4) algorithm, wherer is the maximal number of operations per job.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Brucker P (1988) An efficient algorithm for the job-shop problem with two jobs. Computing 40:353–359

    Article  MATH  MathSciNet  Google Scholar 

  2. Brucker P (1994) A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs. OR Spektrum 16:5–7

    Article  MATH  MathSciNet  Google Scholar 

  3. Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann Discrete Math 5:287–326

    MATH  MathSciNet  Google Scholar 

  4. Jackson IR (1956) An extension of Johnson's results on job lot scheduling. Nav Res Log Quart 3:201–203

    Google Scholar 

  5. Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discr Math 1:343–362

    Article  MATH  MathSciNet  Google Scholar 

  6. Sotskov YuN (1985) Optimal scheduling two jobs with regular criterion. Design Process Automating, Institute of Engineering Cybernetics, 86–95 (in Russian)

  7. Sotskov YuN, Shakhlevich NV (1990) NP-hardness of the problems of optimal scheduling three jobs. Vesti Akad Navuk BSSR Ser Fiz-Mat Navuk 4:96–101 (in Russian)

    MATH  MathSciNet  Google Scholar 

  8. Sotskov YuN, Shakhlevich NV (1995) NP-hardness of shop-scheduling problems with three jobs. Discrete Appl Math 59:237–266

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Engineering Cybernetics of the Academy of Sciences of Belarus, Surganova St. 6, 220012, Minsk, Belarus

    Svetlana A. Kravchenko & Yuri N. Sotskov

Authors
  1. Svetlana A. Kravchenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuri N. Sotskov
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by Belarussian Fundamental Research Found, Project Φ60–242, and Deutsche Forschungsgemeinschaft, Project ScheMA

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kravchenko, S.A., Sotskov, Y.N. Optimal makespan schedule for three jobs on two machines. Mathematical Methods of Operations Research 43, 233–238 (1996). https://doi.org/10.1007/BF01680374

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01680374

Key words

Search

Navigation