Skip to main content
SpringerLink
Log in

Mixed integer programming formulations for the Biomass Truck Scheduling problem

  • Original Paper
  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms and applications. Prentice-Hall, Englewood Cliffs

    Google Scholar 

  • Artigues C, Michelon P, Reusser S (2003) Insertion techniques for static and dynamic resource-constrained project scheduling. Eur J Oper Res 149:249–267

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Demeulemeester E (1995) Minimizing resource availability costs in timelimited project networks. Manage Sci 41:1590–1598

    Article  Google Scholar 

  • Durbin M, Hoffman K (2008) The dance of the thirty-ton trucks: dispatching and scheduling in a dynamic environment. Oper Res 56:3–19

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Gold S, Seuring S (2011) Supply chain and logistics issues of bio-energy production. J Clean Prod 19:32–42

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Hall NG, Potts CN, Sriskandarajah C (2000) Parallel machine scheduling with a common server. Discrete Appl Math 102:223–243

    Article  Google Scholar 

  • Judd JD, Sarin SC, Cundiff JS (2012) Design, modeling, and analysis of a feedstock logistics system. Bioresource Technol 103:209–218

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Kinable J, Wauters T, Vanden Berghe G (2014) The concrete delivery problem. Comput Oper Res 48:53–68

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Koulamas CP (1996) Scheduling two parallel semiautomatic machines to minimize machine interference. Comput Oper Res 23:945–956

    Article  Google Scholar 

  • Kravchenko SA, Werner F (1997) Parallel machine scheduling problems with a single server. Math Comput Model 26:1–11

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Möhring RH (1984) Minimizing costs of resource requirements in project networks subject to a fixed completion time. Oper Res 32:89–120

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Pritsker AAB, Watters LJ, Wolfe PM (1969) Multi-project scheduling with limited resources: a zero-one programming approach. Manage Sci 16:93–108

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Rieck J, Zimmermann J, Gather T (2012) Mixed-integer linear programming for resource leveling problems. Eur J Oper Res 221:27–37

    Article  Google Scholar 

  • Rodrigues SB, Yamashita DS (2010) An exact algorithm for minimizing resource availability costs in project scheduling. Eur J Oper Res 206:562–568

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • Voytenko Y, Peck P (2012) Organisational frameworks for straw-based energy systems in Sweden and Denmark. Biomass Bioenergy 38:34–48

    Article  Google Scholar 

  • Wagner HM (1959) An integer linear programming model for machine scheduling. Nav Res Logist Q 6:131–140

    Article  Google Scholar 

  • Yamashita DS, Armentano VA, Laguna M (2007) Robust optimization models for project scheduling with resource availability cost. J Sched 10:67–76

    Article  Google Scholar 

  • Yan S, Lai W, Chen M (2008) Production scheduling and truck dispatching of ready mixed concrete. Transport Res E-Log 44:164–179

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Business and Economics, University of Pécs, Rákóczi Str. 80, Pecs, 7622, Hungary

    László Torjai & Ferenc Kruzslicz

Authors
  1. László Torjai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ferenc Kruzslicz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to László Torjai.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-015-0395-6

Keywords

Search

Navigation