24Jul 2017

SOLVING OSSP WITH RELEASE DATES TO MINIMIZING THE MAKESPAN AND RESOURCE IDLENESS ? A HYPOTHETICAL CASE.

  • Assistant Professor & Head, PG & Research Department of Mathematics, AA Govt. Arts College, Cheyyar, Tamil Nadu- 604 407.
  • Assistant Professor, PG & Research Department of Mathematics, Shanmuga Industries Arts & Science College, Tiruvannamalai, Tamil Nadu ? 606 601.
Crossref Cited-by Linking logo

  • Abstract
  • Keywords
  • References
  • Cite This Article as
  • Corresponding Author

Scheduling has become one of the major fields within Operations Research with several hundred papers published in every year. In this paper we are considering the open shop scheduling problem with release dates for the objective of minimizing makespan and resource idleness of machines for the hypothetical situation when some jobs need not processed on some machines. Here pre-emption is not allowed. In 2014, we developed an algorithm for the OSSP problem with release dates to minimize makespan and now we tested weather the same algorithm performs well for the objective of resource idleness of the machines for the hypothetical case also. It was found that the proposed algorithm performs better than the existing algorithm with respect to both the objectives.

  1. Aksjonov V A (1988). A polynomial time algorithm of approximate solution of a scheduling problem (in Russian). Upravlyaemyesistemy, 28, 8-11.
  2. Bai D & Tang L (2013). Open shop scheduling problem to minimize makespan with release dates. Applied Mathematical Modelling, 37, 2008-2015.
  3. Barany I & Fiala T (1982). Nearly optimum solution of multi-machine scheduling problems. Szigma, 15,177-191(In Hungarian).
  4. Blazewicz J, Pesch E, Sterna M & Wesner F (2004). Open shop scheduling with late work criteria. Discrete Applied Mathematics, 134, 1-24.
  5. Brucker P, Hurink J, Jurisch B & WostmannB(1997). A branch & bound algorithm for the open-shop problem. Discrete Applied Mathematics. 76, 43-59.
  6. Chen B & Strusevich V A (1993). Approximation algorithms for three-machine open shop ? ORSA Journal of Computing, 5, 321-326.
  7. Chen B, Potts C N & Woeginger G J (1998). A review of machine scheduling: complexity, algorithms and approximability, in;D.-Z.Du et al. (Eds.), Handbook of Combinational Optimization, Kluwer Academic Publishers, 21-169.
  8. Chen B, Vestjens A P A & Woeginger G J (1998). On-line Scheduling of two-machine open shops where jobs arrive over time. Journal of combinatorial optimization, 1, 355-365.
  9. Chen R (2003). Dense schedules for open-shop with jobs release dates. OR Transactions, 7, 73-77.
  10. Chen R, Huang W & Tang G (2008). Dense open-shop schedules with release times. Theoretical Computer science, 407,? 389-399.
  11. Dorndorf U, Pesch E & Phan-Huy T (2001). Solving the open shop scheduling problem.? Journal of? Scheduling , 4, 157-174.
  12. French S (1982). Sequencing and scheduling; an introduction to the mathematics of job shop. Horwood, Chichester.
  13. Gonzalez T & Sahni S (1976). Open shop scheduling to minimize finish times. Journal of association for Computer science, 23, 665-679.
  14. Graham R L, Lawler E L, Lenstra J K & Rinnooykan A H G (1979). Optimization and approximation in deterministic machine scheduling; a survey. Annals of Discrete Mathematics, 5, 287-326.
  15. Jayakumar S (2000). A heuristic approach for solving open shop scheduling problems, minimizingmakespan and resource idleness. Ph.D., thesis, Anna University, Chennai, Tamil Nadu.
  16. Jayakumar S & Meganathan R (2014). Heuristic approach for OSSP to minimize makespanwith release dates. Industrial Engineering Journal, 7(8), 17-22.
  17. Lawler E L, Lenstra J K & Rinnooykan A H G (1981). Minimizing maximum lateness in a two-machine open shop.? Mathematics of Operations Research, 6,153-158.
  18. Lawler E L, Lenstra J K, Rinnooykan A H G & Shmoys D B (1993). Sequencing and Scheduling: algorithms and complexity, in: Graves S C, Rinnooykan A H G, Zipkin P H (Eds.), Handbook in Operations Research and Management Science, Logistics of Production and Inventory, North-Holland, Amsterdam, 4, 445-522.
  19. Pinedo M (2002). Scheduling: Theory, Algorithms and Systems. second ed., Prentice-Hall, New Jersey.
  20. Sgall J (1998). On-line scheduling, in: Fiat A, Woeginger G J (Eds.) (1998), Online algorithms: The state of the Art. Lecture Notes in Computer Science, Springer, Berlin, 1442, 196-231.
  21. Sevastianov S V & Woeginger G J (1998). Makespan minimization in open shops: a polynomial time approximation scheme. Mathematical programming, 82, 191-198.
  22. Strusevich V A (1998). A greedy open shop heuristic with job priorities. Annals of Operations Research, 83, 253-270.
  23. Williamsom D P, Hall L A , Hoogeveen H A, Hurkens C A J, Lenstra J K, Sevast?janov S V & Shmoys D B (1997). Short shop schedules. Operations Research , 45, 288-294.

[S. Jayakumar and R. Meganathan. (2017); SOLVING OSSP WITH RELEASE DATES TO MINIMIZING THE MAKESPAN AND RESOURCE IDLENESS ? A HYPOTHETICAL CASE. Int. J. of Adv. Res. 5 (Jul). 1574-1579] (ISSN 2320-5407). www.journalijar.com

R. MEGANATHAN
Assistant Professor, PG & Research Department of Mathematics, Shanmuga Industries Arts & Science College, Tiruvannamalai, Tamil Nadu – 606 601.

DOI:

Article DOI: 10.21474/IJAR01/4871      
DOI URL: https://dx.doi.org/10.21474/IJAR01/4871

Download Full Paper

Download PDF No. of Downloads: 14 | No. of Views: 84