MPM Job-shop under Availability Constraints
Keywords:
genetic algorithm, geometric approach, assignment heuristicAbstract
A large part of scheduling literature assumes that machines are available all the time. In this paper, the MPM Job-shop scheduling problem, where the machine maintenance has to be performed within certain time intervals inducing machine unavailability, is studied. Two approaches to solve the problem are proposed. The first is a two-phase approach where the assignment and the sequencing are solved separately. The second is an integrated approach based on the exact resolution of the 2-job problem using the geometric approach.References
Adiri I., Bruno J., Frostig E., and Rinnooy Kan A. H. G. : Single machine flow-time with a single breakdown. Acta Informatica, 26, 679-696. http://dx.doi.org/10.1007/BF00288977
S.B. Akers et J. Friedman. - A non-numerical approach to production scheduling problems. Operations Research, vol. 3, 1955, pp. 3, 429-442. http://dx.doi.org/10.1287/opre.3.4.429
Aggoune, R.: Ordonnancement d'Ateliers sous Contraintes de Disponibilité des Machines(2002) Ph.D. Thesis, Université de Metz, France.
Aggoune, R.: Two-job shop Scheduling Problems with availability Constraints. ICAPS 2004, June 3-7, 2004, Whistler, British Columbia, Canada.
Duta, L.: Contribution ´r l'étude de la conduite des systˇcmes de désassemblage.These (2006). Université de Franche-Comté Université de Bucarest.
Duta,L., Filip, F. G. Henrioud,J.-M. Popescu: Disassembly Line Scheduling with Genetic Algorithms. Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. III (2008), No. 3, pp. 270-280.
Filip F.G., Neagu G. and Donciulescu D. (1983). Job shop scheduling optimization in real time production control. Computers in Industry, 4(4) (North Holland, Amsterdam), 395 - 403. http://dx.doi.org/10.1016/0166-3615(83)90006-4
Ruiz-Torres AJ., Nakatani K.: Application of real-time simulation to assign due dates on logisticmanufacturing networks. Proceedings of the 1998 Winter Simulation Conference.
Blazewicz J., Breit J., Formanowicz P., Kubiak W., Schmidt G.: Heuristic algorithms for the twomachine flowshop problem with limited machine availability. Omega Journal (2001), 29, 599-608. http://dx.doi.org/10.1016/S0305-0483(01)00048-2
Carlier J.: Scheduling jobs with release dates and tails on identical machines to minimize the makespan. European Journal of Operational research(1987), 29:298-306, North-Holland. http://dx.doi.org/10.1016/0377-2217(87)90243-8
Carlier J.: The One-Machine Sequencing Problem, European Jounal of operational research(1982), 11: 42-47.
Jurisch B.: Scheduling Jobs in Shops with Multi Purpose Machines (1992) Ph.D Thesis, Universität Osnabrück.
J. Hurink, B. Jurisch et M. Thole. - Tabu search for the job-shop scheduling problem with multipurpose machines. Operations Research Spektrum, vol. 15, 1994, pp. 205-215. http://dx.doi.org/10.1007/BF01719451
Kubiak W., Blazewicz J., Formanowicz P., Breit J., Schmidt G.: Two-machine flow shops with lim-ited machine availability. European Journal of Opera-tional Research (2002) 136: 528-540. http://dx.doi.org/10.1016/S0377-2217(01)00083-2
Lee C.Y.: Machine scheduling with an availability constraint. Journal of Global Optimization(1996) 9: 395-416. http://dx.doi.org/10.1007/BF00121681
Glover F., Laguna M.: Tabu search, Kluwer Publish- ers, Boston 1997.
Jurisch, B., (1995). Lower bounds for the job-shop scheduling problem on multi-purpose machines. Discrete Applied Mathematics, 58, 145-156. http://dx.doi.org/10.1016/0166-218X(93)E0124-H
Lee C.Y.: Minimizing the mazkespan in two-machine flows-hop scheduling with availability constraint. Operations research letters (1997), 20: 129-139, . http://dx.doi.org/10.1016/S0167-6377(96)00041-7
Lee C.Y.: Two-machine flowshop scheduling with availability constraints. European Journal of Opera-tional Research (1999), 114: 420-429. http://dx.doi.org/10.1016/S0377-2217(97)00452-9
Lee KM., Yamakawa T.: A Genetic algorithm for general machine scheduling problems. Int.Conf. on Conventional and knowledge-Based Electronics Systems, Vol 2 pp60-66 Australia, 1998. http://dx.doi.org/10.1109/kes.1998.725893
Mati, Y., and Xie, X.: Un algorithme polonimial pour le job shop flexible avec blocage : cas de deux jobs. Mosim'2003, April 23-25 april, Toulouse, France.
Mati, Y., and Xie, X.: The complexity of two-job shop problems with multi-purpose unrelated machines. European Journal of Operational Research, 152 (1), 159-169, 2004. http://dx.doi.org/10.1016/S0377-2217(02)00675-6
Nowicki E., Smutnicki C.: A Fast Taboo Search Algorithm for the Job-Shop Problem, Management Science (1996), Vol. 42, No. 6, pp. 797-813. http://dx.doi.org/10.1287/mnsc.42.6.797
Schmidt G.: Scheduling on semi identical processors. Z. Oper.Res.1984, A28, 153-162, . http://dx.doi.org/10.1007/bf01920917
Schmidt G.: Scheduling independent tasks with deadlines on semi-identical processors. Journal of Operational research society, 39, 271-277, 1988. http://dx.doi.org/10.1057/jors.1988.44
Sanjay J., William J. Foley :Impact of Interruptions of Schedule Execution in Flexible Manufacturing Systems. The International Journal of Flexible Manufacturing Systems, 14, 319-344, 2002. http://dx.doi.org/10.1023/A:1020952823369
Roy B., Sussmann B.: Les probl'emes d'ordonnancement avec contraintes disjonctives (in French). Technical Report 9 bis, SEMA, Paris (France), December 1964.
Leon V. J., Wu S. D.: On scheduling with ready-times, due-dates and vacations. Naval Research Logistics, 39:53-65, 1992. http://dx.doi.org/10.1002/1520-6750(199202)39:13.0.CO;2-C
Schmidt G.: Scheduling with limited machine availability. European Journal of Operational Research (2000), 121, 1-15. http://dx.doi.org/10.1016/S0377-2217(98)00367-1
Mauguiere Ph., Billaut J-C., Bouquard J-L.: New single machine and job-shop scheduling problems with availability constraints. Journal of Scheduling, 2004.
Zribi N. : Ordonnancement des job-shop flexibles sous contraintes de disponibilité des machines. PHD Thesis, Ecole Centrale de Lille, France, 2005.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
