CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Mixed Integer Linear Programs for Blocking and No Wait Job Shop Scheduling Problems in Robotic cells

by Saad Louaqad, Oulaid Kamach
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 153 - Number 10
Year of Publication: 2016
Authors: Saad Louaqad, Oulaid Kamach
10.5120/ijca2016912158

Saad Louaqad, Oulaid Kamach . Mixed Integer Linear Programs for Blocking and No Wait Job Shop Scheduling Problems in Robotic cells. International Journal of Computer Applications. 153, 10 ( Nov 2016), 1-7. DOI=10.5120/ijca2016912158

@article{ 10.5120/ijca2016912158,
author = { Saad Louaqad, Oulaid Kamach },
title = { Mixed Integer Linear Programs for Blocking and No Wait Job Shop Scheduling Problems in Robotic cells },
journal = { International Journal of Computer Applications },
issue_date = { Nov 2016 },
volume = { 153 },
number = { 10 },
month = { Nov },
year = { 2016 },
issn = { 0975-8887 },
pages = { 1-7 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume153/number10/26436-2016912158/ },
doi = { 10.5120/ijca2016912158 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:58:44.620895+05:30
%A Saad Louaqad
%A Oulaid Kamach
%T Mixed Integer Linear Programs for Blocking and No Wait Job Shop Scheduling Problems in Robotic cells
%J International Journal of Computer Applications
%@ 0975-8887
%V 153
%N 10
%P 1-7
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper studies the problem of scheduling Job shops in robotic cells with no intermediate buffers, called No Wait Blocking Transport Job Shop Scheduling Problem (NWBT JSSP). This problem is an extension of the classical job shop problem. No Wait Blocking Transport job shop problems arise in many realistic production environments. To tackle this problem, we developed a Mixed Integer Linear Program and proposed a constructive heuristic based on priority rules. The MILP model has been used to solve optimally problems with as many as ten jobs, ten machines and three robots. Computational results on hypothetically generated test problems are discussed and suggestions of future research projects are proposed.

References
  1. A.S. Jain, S. Meeran, Deterministic job-shop scheduling: Past present and future, European Journal of Operational Research 113 (1999) 390-434.
  2. N.G. Hall, C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process, Operations Research 44 (3) (1996) 510-525.
  3. O. Candar, Machine scheduling problems with blocking and no-wait in process, Working Paper [April-99], Department of Industrial Engineering, Bilkent University, Ankara, Turkey, 1999.
  4. Mascis, D. Pacciarelli, Machine scheduling via alternative graphs, Research Report, RT-DIA-46-2000, Italy, 2000.
  5. A. Mascis, D. Pacciarelli, Job-shop scheduling with blocking and no-wait constraints, European Journal of Operational Research 143 (2002) 498-517.
  6. Y. Mati, N. Rezg, X. Xie, Geometric approach and taboo search for scheduling flexible manufacturing systems, IEEE Transactions on Robotics and Automation 17 (6) (2001) 805-818.
  7. C.A. Brizuela, Y. Zhao, N. Sannomiya, No-wait and blocking job-shops: Challenging problems for GA’s, IEEE 0-7803-77-2/ 01 (2001) 2349-2354.
  8. A. Klinkert, Optimization in design and control of automated high-density warehouses, Doctoral Thesis No. 1353, University of Fribourg, Switzerland, 2001.
  9. H. Groflin, A. Klinkert, Local search in job shop scheduling with synchronization and blocking constraints, Internal working paper [04-06], Department of Informatics, University of Fribourg, Switzerland, 2004.
  10. P. Brucker, T. Kampmeyer, Cyclic job shop scheduling problems with blocking,Ann. Oper. Res. 159 (2008) 161181.
  11. A. AitZai, B. Benmedjdoub, M. Boudhar, A branch and bound and parallel genetic algorithm for the job shop scheduling problem with blocking, Int. J. Oper. Res.14 (3) (2012) 343365.
  12. J. Grabowski, J. Pempera, Sequencing of jobs in some production system, European Journal of Operation Research 125 (2000) 535550.
  13. D. Pacciarelli, M. Pranzo, Production scheduling in a steelmaking-continuous casting plant, Computer and Chemical Engineering 28 (2004) 28232835.
  14. J. Romero, L. Puigjaner, T. Holczinger, F. Friedler, Scheduling intermediate storage multipurpose batch plants using the S-graph, AIChE J. 50 (2004) 403417.
  15. L. Chen, N. Bostel, P. Dejax, J. Cai, L. Xi, A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal, European Journal of Operation Research 18 (2007) 4058.
  16. A. DAriano, D. Pacciarelli, M. Pranzo, A branch and bound algorithm for scheduling trains in a railway network, European Journal of Operation Research 183 (2007) 643657.
  17. J. Hurink ,S. Knust, Tabu search algorithms for job-shop problems with a single transport robot, European Journal of Operational Research 2005;162(1):99111.
  18. J. Blazewicz,H. Eiselt ,G. Finke,G. Laporte,J. Weglarz, Scheduling tasks and vehicles in a flexible manufacturing system, International Journal of Flexible Manufacturing Systems 1991;4(1):516.
  19. U. Bilge,G. Ulusoy, A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research 1995;43(6):105870.
  20. G. Ulusoy, F. Sivrikaya-erifolu, U. Bilge, A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles, Computers & Operations Research 1997;24(4):33551.
  21. G. Alvarenga,G. Mateus, G. De Tomi, A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Computers & Operations Research 2007;34(6):156184.
  22. M. Soylu,N. O zdemirel, S. Kayaligil, A self-organizing neural network approach for the single AGV routing problem, European Journal of Operational Research 2000;121(1):12437.
  23. J. Hurink,S. Knust, A tabu search algorithm for scheduling a single robot in a job shop environment, Discrete Applied Mathematics 2002;119(12):181203.
  24. T. Abdelmaguid,A. Nassef, B. Kamal, M. Hassan, A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles, International Journal of Production Research 2004;42(2):26781.
  25. P. Lacomme,M. Larabi, N. Tchernev, A disjunctive graph for the job shop with several robots, In: MISTA conference; 2007. p. 28592.
  26. L. Deroussi, M. Gourgand, N. Tchernev, A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles, International Journal of Production Research 2008;46(8):214364.
  27. H. Gong, L. Tang, Two-machine flow shop scheduling with intermediate transportation under job physical space consideration, Computers & Operations Research 2011;8(9):126774.
  28. M. Mateo, R. Companys, J. Bautista, Resolution of graphs with bounded cycle time for the cyclic hoist scheduling problem, In: 8th International Workshop on Project Management and Scheduling. Cite seer; 2002. p. 25760.
  29. A. Caumond, P. Lacomme, A. Moukrim, N. Tchernev, An MILP for scheduling problems in an FMS with one vehicle, European Journal of Operational Research 2009;199(3):70622.
  30. Y. Crama, J. Van de Klundert, Cyclic scheduling of identical parts in a robotic cell. Operations Research 1997;45(6):95265.
  31. N. Brauner, G. Finke, V. Lehoux-Lebacque, C. Potts, J. Whitehead, Scheduling of coupled tasks and one machine no wait robotic cells, Computers & Operations Research 2009;36(2):3017.
  32. AI. Corra, A. Langevin, L-M. Rousseau, Scheduling and routing of automated guided vehicles: a hybrid approach. Computers & Operations Research 2007; 34(6):1688707, [part special Issue: Odysseus 2003 second international workshop on freight transportation logistics. doi:10.1016/j.cor.2005.07.004].
  33. E. Stafford, F. Tseng,J. Gupta, Comparative evaluation of MILP flow shop models, Journal of Operations Research Society 2005; 56;88101.
  34. A. Manne, On the job shop scheduling problem. Operations Research 1960;8,21922
Index Terms

Computer Science
Information Sciences

Keywords

Job Shop Scheduling problem Transport Constraint Blocking Constraint No Wait Constraint Mixed Integer Linear Program

Powered by PhDFocusTM