Abstract
In this paper, we introduce the Biomass Truck Scheduling (BTS) problem that originated in a real-life herbaceous biomass supply chain (HBSC) around Pécs, Hungary. BTS can be considered as a Parallel Machine Scheduling with a Single Server problem, where identical trucks (parallel machines) deliver biomass from satellite storage locations to a central biorefinery operating a single unloader (single server). We make two particular assumptions regarding the server: the server operation has a unit time length for each trip and idle periods are not allowed for it (server no idle time constraint). We consider two objective functions associated with the revealed HBSC logistic cost structure. First, the number of trucks is minimized (resource availability cost) following which the total truck idle time is minimized. Three mixed integer programming formulations are constructed to solve BTS, and their efficiency is evaluated using a number of test cases. We found that, even if the number of trucks is locked at its minimum value, there is always a schedule with zero truck idle time—that is, there is no trade-off between these two objective functions.
Similar content being viewed by others
References
Abdekhodaee AH, Wirth A (2002) Scheduling parallel machines with a single server: some solvable cases and heuristics. Comput Oper Res 29:295–315
Abdekhodaee AH, Wirth A, Gan HS (2004) Equal processing and equal setup times cases of scheduling parallel machines with a single server. Comput Oper Res 31:1867–1889
Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms and applications. Prentice-Hall, Englewood Cliffs
Artigues C, Michelon P, Reusser S (2003) Insertion techniques for static and dynamic resource-constrained project scheduling. Eur J Oper Res 149:249–267
Brucker P, Dhaenens-Flipo C, Knust S, Kravchenko SA, Werner F (2002) Complexity results for parallel machine problems with a single server. J Sched 5:429–457
Demeulemeester E (1995) Minimizing resource availability costs in timelimited project networks. Manage Sci 41:1590–1598
Durbin M, Hoffman K (2008) The dance of the thirty-ton trucks: dispatching and scheduling in a dynamic environment. Oper Res 56:3–19
Gan HS, Wirth A, Abdekhodaee A (2012) A branch-and-price algorithm for the general case of scheduling parallel machines with a single server. Comput Oper Res 39:2242–2247
Gold S, Seuring S (2011) Supply chain and logistics issues of bio-energy production. J Clean Prod 19:32–42
Guirchoun S, Martineau P, Billaut JC (2005) Total completion time minimization in a computer system with a server and two parallel processors. Comput Oper Res 32:599–611
Hall NG, Potts CN, Sriskandarajah C (2000) Parallel machine scheduling with a common server. Discrete Appl Math 102:223–243
Judd JD, Sarin SC, Cundiff JS (2012) Design, modeling, and analysis of a feedstock logistics system. Bioresource Technol 103:209–218
Kim MY, Lee YH (2012) MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Comput Oper Res 39:2457–2468
Kinable J, Wauters T, Vanden Berghe G (2014) The concrete delivery problem. Comput Oper Res 48:53–68
Koné O, Artigues C, Lopez P, Mongeau M (2011) Event-based MILP models for resource-constrained project scheduling problems. Comput Oper Res 38:3–13
Koulamas CP (1996) Scheduling two parallel semiautomatic machines to minimize machine interference. Comput Oper Res 23:945–956
Kravchenko SA, Werner F (1997) Parallel machine scheduling problems with a single server. Math Comput Model 26:1–11
Kravchenko SA, Werner F (1998) Scheduling on parallel machines with a single and multiple servers. Otto-von-Guericke-Universitat Magdeburg. Preprint 30(98):1–18
Möhring RH (1984) Minimizing costs of resource requirements in project networks subject to a fixed completion time. Oper Res 32:89–120
Mukunda A, Ileleji KE, Wan H (2006) Simulation of corn stover logistics from on-farm storage to an ethanol plant. In: ASABE annual international meeting. ASABE Paper No. 066177. ASABE: St. Joseph, Mich
Ou J, Qi X, Lee CY (2010) Parallel machine scheduling with multiple unloading servers. J Sched 13:213–226
Pritsker AAB, Watters LJ, Wolfe PM (1969) Multi-project scheduling with limited resources: a zero-one programming approach. Manage Sci 16:93–108
Ranjbar M, Kianfar F, Shadrokh S (2008) Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm. Appl Math Comput 196:879–888
Ravula PP, Grisso RD, Cundiff JS (2008) Comparison between two policy strategies for scheduling trucks in a biomass logistic system. Bioresource Technol 99:5710–5721
Rieck J, Zimmermann J, Gather T (2012) Mixed-integer linear programming for resource leveling problems. Eur J Oper Res 221:27–37
Rodrigues SB, Yamashita DS (2010) An exact algorithm for minimizing resource availability costs in project scheduling. Eur J Oper Res 206:562–568
Sokhansanj S, Hess JR (2009) Biomass supply logistics and infrastructure. In: Mielenz Jonathan (ed) Biofuels methods and protocols. Humana Press, New York, pp 1–25
Thörnblad K (2011) On the optimization of schedules of a multitask production cell. Chalmers University of Technology, Preprint 19(2011):1–64
Unlu Y, Mason SJ (2010) Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Comput Ind Eng 58:785–800
Voytenko Y, Peck P (2012) Organisational frameworks for straw-based energy systems in Sweden and Denmark. Biomass Bioenergy 38:34–48
Wagner HM (1959) An integer linear programming model for machine scheduling. Nav Res Logist Q 6:131–140
Yamashita DS, Armentano VA, Laguna M (2007) Robust optimization models for project scheduling with resource availability cost. J Sched 10:67–76
Yan S, Lai W, Chen M (2008) Production scheduling and truck dispatching of ready mixed concrete. Transport Res E-Log 44:164–179
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Torjai, L., Kruzslicz, F. Mixed integer programming formulations for the Biomass Truck Scheduling problem. Cent Eur J Oper Res 24, 731–745 (2016). https://doi.org/10.1007/s10100-015-0395-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-015-0395-6