×

zbMATH — the first resource for mathematics

A job-shop scheduling approach for optimising sugarcane rail operations. (English) Zbl 1230.90095
Summary: The sugarcane transport system is very complex and uses a daily schedule, consisting of a set of locomotives runs, to satisfy the requirements of the mill and harvesters. The total cost of sugarcane transport operations is very high; over 35% of the total cost of sugarcane production in Australia is incurred in cane transport. Producing efficient schedules for sugarcane transport can reduce the cost and limit the negative effects that this system can have on the raw sugar production system. In this paper, the sugarcane rail operations are formulated as a blocking job shop scheduling problem. A mixed integer programming approach is used to formulate the shop job scheduling problem. Mixed integer programming and constraint programming search techniques are integrated for solving the problem. A case study is solved to test the approach.

MSC:
90B35 Deterministic scheduling theory in operations research
90B90 Case-oriented studies in operations research
Software:
OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbass HA, Sarker A, Newton C (2001) A Pareto-frontier differential evolution approach for multi-objective optimization problems, proceedings of the congress on evolutionary computation 2001 (CEC’2001), vol. 2. IEEE Service Center, Piscataway, New Jersey. pp 971–978
[2] Ariano AD, Pacciarelli D, Pranzo M (2007) A branch and bound algorithm for scheduling trains in a railway network. Eur J Oper Res 183:643–657 · Zbl 1179.90135 · doi:10.1016/j.ejor.2006.10.034
[3] Artigues C, Gendreau M, Rousseau LM, Vergnaud A (2009) Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound. Comput Oper Res 36:2330–2340 · Zbl 1179.90119 · doi:10.1016/j.cor.2008.08.013
[4] Beck JC, Perron L (2000) Discrepancy-bounded depth first search. In: Proceedings of the second international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems. CP-AI-OR 2000. pp 21–22
[5] Beck JC, Refalo P (2003) A hybrid approach to scheduling with earliness and tardiness costs. Ann Oper Res 118:49–71 · Zbl 1026.90039 · doi:10.1023/A:1021849405707
[6] Burdett RL, Kozan E (2010a) A sequencing approach for creating new train timetables. OR Spectrum 32(1):163–193 · Zbl 1181.90112 · doi:10.1007/s00291-008-0143-6
[7] Burdett RL, Kozan E (2010b) A disjunctive graph model and framework for constructing new train schedules. Eur J Oper Res 200(1):85–98 · Zbl 1187.90129 · doi:10.1016/j.ejor.2008.12.005
[8] Dovier A, Formisano A, Pontelli E (2009) An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. J of Exp Theor Artif Intell 21(2):79–121 · Zbl 1193.68073 · doi:10.1080/09528130701538174
[9] El Khayat G, Langevin A, Riopel D (2006) Integrated production and, material handling scheduling using mathematical programming and constraint programming. Eur J Oper Res 175:1818–1832 · Zbl 1142.90371 · doi:10.1016/j.ejor.2005.02.077
[10] Guel A, Barber F (2009) Mathematical solutions for solving periodic railway transportation. Math Probl in Eng 60:19. ID 728916. doi: 10.1155/2009/728916 · Zbl 1181.90126
[11] Hasan SMK, Sarker R, Essam D, Cornforth D (2009a) A genetic algorithm with priority rules for solving job-shop scheduling problems. Nat Intell Sched Plan Pack Prob 250:55–88
[12] Hasan SMK, Sarker R, Essam D, Cornforth D (2009b) Memetic algorithms for solving job-shop scheduling problems. Memet Comput 1(1):69–83 · doi:10.1007/s12293-008-0004-5
[13] Hentenryck PV (2002) Constraint and integer programming in OPL. INFORMS J Comput 14(4):345–372 · Zbl 1238.90102 · doi:10.1287/ijoc.14.4.345.2826
[14] Hentenryck PV, Michel L (2005) Constraint-based local search. The MIT Press, Cambridge
[15] Her JH, Ramakrishna RS (2007) An external-memory depth-first search algorithm for general grid graphs. Theor Comput Sci 374:170–180 · Zbl 1162.05358 · doi:10.1016/j.tcs.2006.12.022
[16] Higgins A, Kozan E, Ferreira L (1996) Modelling the number and location of sidings on a single line railway. Comput Oper Res 24(3):209–220 · Zbl 0889.90062 · doi:10.1016/S0305-0548(96)00042-1
[17] Hooker JN (2005) A hybrid method for planning and scheduling. Construction 10:385–401 · Zbl 1122.90054
[18] Liu SQ, Kozan E (2009) Scheduling trains as a blocking parallel-machine job shop scheduling problem. Comput Oper Res 36(10):2840–2852 · Zbl 1160.90476 · doi:10.1016/j.cor.2008.12.012
[19] Martin F, Pinkney A, Xinghuo Y (2001) Cane railway scheduling via constraint logic programming: labelling order and constraints in a real-live application. Ann Oper Res 108:193–209 · Zbl 1001.90506 · doi:10.1023/A:1016067230126
[20] Mascis A, Pacciarelli D (2002) Job-shop scheduling with blocking and no-wait constraints. Eur J Oper Res 143:498–517 · Zbl 1082.90528 · doi:10.1016/S0377-2217(01)00338-1
[21] Masoud M, Kozan E, Kent G (2010) Scheduling techniques to optimise sugarcane rail systems. ASOR Bull 29:25–34
[22] Murali P, Dessouky MM, Ordóñez F, Palmer K (2009) A delay estimation technique for single and double-track railroads. Logist Transp Rev. doi: 10.1016/j.tre.2009.04.016
[23] Oliveira ES (2001) Solving single track railway scheduling problem by using constraint programming. PhD dissertation, the University of Leeds
[24] Rodriguez J (2007) A constraint programming model for real-time train scheduling at junctions. Transp Res Part B 41:231–245 · doi:10.1016/j.trb.2006.02.006
[25] Rossi A, Boschi E (2009) A hybrid heuristic to solve the parallel machines job-shop scheduling problem. Adv Eng Softw 40:118–127 · Zbl 1156.90370 · doi:10.1016/j.advengsoft.2008.03.020
[26] Sierra MR, Varela R (2008) Pruning by dominance in best-first search for the job shop scheduling problem with total flow time. J Intell Manuf. doi: 10.1007/s10845-008-0167-4
[27] Su Yun Y, Gen M (2002) Advanced scheduling problem using constraint programming techniques in SCM environment. Comput Ind Eng 43(1–2):213–229 · doi:10.1016/S0360-8352(02)00065-7
[28] Walsh T (1997) Depth-bounded discrepency search. In Proceedings of the fifteenth international joint conference on artificial intelligence. Morgan Kaufmann. pp 1388–1395
[29] Watson JP, Beck JC (2008) A hybrid constraint programming/local search approach to the job-shop scheduling problem. In: Perron L, Trick M (eds) CPAIOR 2008, LNCS 5015. Springer, Berlin, pp 263–277 · Zbl 1142.68527
[30] Yuan J, Hansen IA (2007) Optimizing capacity utilization of stations by estimating knock-on train delays. Transp Res Part B 41:202–217 · doi:10.1016/j.trb.2006.02.004
[31] Zhou X, Zhong M (2007) Single-track train timetable with guaranteed optimality: branch-and bound algorithms with enhanced lower bounds. Trans Res Part B 41:320–341 · doi:10.1016/j.trb.2006.05.003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.