Abstract
This paper extends the traditional job shop scheduling problem (JSP) by incorporating the routing and scheduling decisions of the material handling equipment. It provides a generic definition and a mixed integer linear programming model for the problem considering the case of heterogeneous multiple-load material handling equipment. A constructive heuristic is developed for solving the problem. This heuristic is based on the well-known Giffler and Thompson’s algorithm for the JSP with modifications that account for the routing decisions of the material handling equipment and their effect on the start times of the manufacturing operations. Different dispatching rules are integrated into the heuristic, and experiments are conducted to study their effect on the makespan along with the determination of the computational time requirements of the developed heuristic.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Jain AS, Meeran S (1999) Deterministic job-shop scheduling: Past, present and future. Eur J Oper Res 113:390–434. doi:10.1016/S0377-2217(98)00113-1
Smith JS, Peters BA, Srinivasan A (1999) Job shop scheduling considering material handling. Int J Prod Res 37:1541–1560. doi:10.1080/002075499191968
Fisher EL, Farber JB, Kay MG (1988) MATHES: An expert system for material handling equipment selection. Eng Costs Prod Econ 14(4):297–310. doi:10.1016/0167-188X(88)90034-1
Ganesharajah T, Hall NG, Sriskandarajah C (1998) Design and operational issues in AGV-served manufacturing systems. Ann Oper Res 76:109–154. doi:10.1023/A:1018936219150
Deb SK, Bhattacharyya B, Sorhkel SK (2003) Facility layout and material handling system selection planning using hybrid methodology. Int J Ind Eng Theory Appl Pract 10(3):289–297
Cho C, Egbelu PJ (2005) Design of a web-based integrated material handling system for manufacturing applications. Int J Prod Res 43(2):375–403. doi:10.1080/0020754042000268866
Maggu PL, Das G (1980) On the 2 × n sequencing problem with transportation time of jobs. Pure Appl Math Sci 12:1–6
Maggu PL, Das G, Kumar R (1981) On equivalent-job for job-block in 2 × n sequencing problem with transportation-times. J Oper Res Soc Jpn 24:136–146
Johnson SM (1954) Optimal two and three stage production schedules with setup times included. Nav Res Logistics Q 1:61–67. doi:10.1002/nav.3800010110
Raman N, Talbot FB, Rachamadugu RV (1986) Simultaneous scheduling of machines and material handling devices in automated manufacturing. Proceedings of 2nd ORSA/TIMS Conference on FMS: OR Models and Applications. Elsevier Science Publishers B.V, Amsterdam, pp 321–332
Hurink J, Knust S (2001) Makespan minimization for flow-shop problems with transportation times and a single robot. Discrete Appl Math 112:199–216. doi:10.1016/S0166-218X(00)00316-4
Che A, Chu C, Chu F (2002) Multicyclic hoist scheduling with constant processing times. IEEE Trans Robot Autom 18(1):69–80. doi:10.1109/70.988976
Liu J, Jiang Y, Zhou Z (2002) Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution. IIE Trans 34:905–914
Che A, Chu C (2005) A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line. Oper Res Lett 33(3):274–284. doi:10.1016/j.orl.2003.10.012
Che A, Chu C (2005) Multi-degree cyclic scheduling of two robots in a no-wait flowshop. IEEE Trans Autom Sci Eng 2(2):173–183. doi:10.1109/TASE.2004.835600
Che A, Chu C (2007) Cyclic hoist scheduling in large real-life electroplating lines. OR Spectrum 29(3):445–470. doi:10.1007/s00291-006-0040-9
Che A, Chu C (2008) Optimal scheduling of material handling devices in a PCB production line: Problem formulation and a polynomial algorithm. Math Probl Eng 2008:364279
Wu SD, Wysk RA (1989) An application of discrete-event simulation to on-line control and scheduling in flexible manufacturing. Int J Prod Res 27:1603–1623. doi:10.1080/00207548908942642
Sabuncuoglu I, Hommertzheim DL (1992) Dynamic dispatching algorithm for scheduling machines and automated guided vehicles in a flexible manufacturing system. Int J Prod Res 30:1059–1079. doi:10.1080/00207549208942943
Bilge U, Ulusoy G (1995) Time window approach to simultaneous scheduling of machines and material handling system in an FMS. Oper Res 43:1058–1070. doi:10.1287/opre.43.6.1058
Ferland JA, Fortin L (1989) Vehicles scheduling with sliding time windows. Eur J Oper Res 38:213–226. doi:10.1016/0377-2217(89)90106-9
Ulusoy G, Sivrikaya-Serifoglu F, Bilge U (1997) A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles. Comput Oper Res 24:335–351. doi:10.1016/S0305-0548(96)00061-5
Abdelmaguid TF, Nassef AO, Kamal BA, Hassan MF (2004) A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles. Int J Prod Res 42:267–281. doi:10.1080/0020754032000123579
Reddy BSP, Rao CSP (2006) A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS. Int J Adv Manuf Technol 31:602–613. doi:10.1007/s00170-005-0223-6
Jawahar N, Aravindan P, Ponnambalam SG, Suresh RK (1998) AGV schedule integrated with production in flexible manufacturing systems. Int J Adv Manuf Technol 14:428–440. doi:10.1007/BF01304622
Anwar MF, Nagi R (1998) Integrated scheduling of material handling and manufacturing activities for just-in-time production of complex assemblies. Int J Prod Res 36:653–681. doi:10.1080/002075498193624
Khayat GE, Langevin A, Riopel D (2006) Integrated production and material handling scheduling using mathematical programming and constraint programming. Eur J Oper Res 175(3):1818–1832. doi:10.1016/j.ejor.2005.02.077
Hurink J, Knust S (2005) Tabu search algorithms for job-shop problems with a single transport robot. Eur J Oper Res 162:99–111. doi:10.1016/j.ejor.2003.10.034
Roy B, Sussmann B (1964) Les problemes d’ordonnancement avec constraints disjonctives. Technical report 9, SEMA, Note D.S., Paris
Caumond A, Lacomme P, Moukrim A, Tchernev N (2008) An MILP for scheduling problems in an FMS with one vehicle. Eur J Oper Res . doi:10.1016/j.ejor.2008.03.051
Ho Y-C, Chien S-H (2006) A simulation study on the performance of task-determination rules and delivery-dispatching rules for multiple-load AGVs. Int J Prod Res 44(20):4193–4222. doi:10.1080/00207540500442401
Lee J, Srisawat T (2006) Effect of manufacturing system constructs on pick-up and drop-off strategies of multiple-load AGVs. Int J Prod Res 44(4):653–673. doi:10.1080/00207540500251646
Desaulniers G, Desrosiers J, Erdmann A, Solomon MM, Soumis F (2002) VRP with pickup and delivery. In: Toth P, Vigo D (eds) The vehicle routing problem. Siam, Philadelphia, pp 225–242
Abdelmaguid TF (2007) Integrated scheduling of manufacturing operations and material handling tasks in the job shops: A network model. Proceedings of the 37th international conference on computers and industrial engineering. Alexandria, Egypt, pp 1951–1960
Anonymous (2003) CPLEX 9.0 User’s Manual, ILOG, Mountain View, CA
Giffler B, Thompson GL (1960) Algorithms for solving production scheduling problems. Oper Res 8:487–503. doi:10.1287/opre.8.4.487
Panwalkar SS, Iskander W (1977) A survey of scheduling rules. Oper Res 25(1):45–61. doi:10.1287/opre.25.1.45
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Abdelmaguid, T.F., Nassef, A.O. A constructive heuristic for the integrated scheduling of machines and multiple-load material handling equipment in job shops. Int J Adv Manuf Technol 46, 1239–1251 (2010). https://doi.org/10.1007/s00170-009-2176-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-009-2176-7