IDEAS home Printed from
   My bibliography  Save this article

A mixed-integer model for solving ordering problems with side constraints


  • Francesco Maffioli
  • Anna Sciomachen


We present an exact approach for solving the Sequential Ordering Problem (SOP). In this problem, a set of jobs has to be processed on a single machine; a time window (deadline - release date) is associated with each job, and precedence relationships between jobs are given. Moreover, a setup time (possibly zero) before processing a job is assigned. The prob-lem consists in finding an ordering of the jobs such that the completion time of the job sequenced last is minimized. Starting from a 0-1 formulation of the problem, we translate the model into a linear Mixed Integer Program (MIP) problem by adding some variables representing the idle time of the machine, in such a way that both the subtour elimination constraints and the due forcing constraints are implicitly satisfied. Some computational experience is reported along with the analysis of a simple case study. The main goal of this work is to assess the suitability of the mathematical models presented with respect to avail-able MIP software like OSL. Copyright Kluwer Academic Publishers 1997

Suggested Citation

  • Francesco Maffioli & Anna Sciomachen, 1997. "A mixed-integer model for solving ordering problems with side constraints," Annals of Operations Research, Springer, vol. 69(0), pages 277-297, January.
  • Handle: RePEc:spr:annopr:v:69:y:1997:i:0:p:277-297:10.1023/a:1018989130169
    DOI: 10.1023/A:1018989130169

    Download full text from publisher

    File URL:
    Download Restriction: Access to full text is restricted to subscribers.

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Amengual, Dante & Sentana, Enrique, 2010. "A comparison of mean-variance efficiency tests," Journal of Econometrics, Elsevier, vol. 154(1), pages 16-34, January.
    2. Gordon J. Alexander & Alexandre M. Baptista, 2004. "A Comparison of VaR and CVaR Constraints on Portfolio Selection with the Mean-Variance Model," Management Science, INFORMS, vol. 50(9), pages 1261-1273, September.
    3. Mencía, Javier & Sentana, Enrique, 2009. "Multivariate location-scale mixtures of normals and mean-variance-skewness portfolio allocation," Journal of Econometrics, Elsevier, vol. 153(2), pages 105-121, December.
    4. Zhenyu Wang, 2005. "A Shrinkage Approach to Model Uncertainty and Asset Allocation," Review of Financial Studies, Society for Financial Studies, vol. 18(2), pages 673-705.
    5. Ling, Shiqing & McAleer, Michael, 2003. "Asymptotic Theory For A Vector Arma-Garch Model," Econometric Theory, Cambridge University Press, vol. 19(02), pages 280-310, April.
    6. Michael W. Brandt & Amit Goyal & Pedro Santa-Clara & Jonathan R. Stroud, 2005. "A Simulation Approach to Dynamic Portfolio Choice with an Application to Learning About Return Predictability," Review of Financial Studies, Society for Financial Studies, vol. 18(3), pages 831-873.
    7. Merton, Robert C. & Samuelson, Paul A., 1974. "Fallacy of the log-normal approximation to optimal portfolio decision-making over many periods," Journal of Financial Economics, Elsevier, vol. 1(1), pages 67-94, May.
    8. Eric Jondeau & Michael Rockinger, 2006. "Optimal Portfolio Allocation under Higher Moments," European Financial Management, European Financial Management Association, vol. 12(1), pages 29-55.
    9. Sébastien Laurent & Luc Bauwens & Jeroen V. K. Rombouts, 2006. "Multivariate GARCH models: a survey," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 21(1), pages 79-109.
    10. J. Tobin, 1958. "Liquidity Preference as Behavior Towards Risk," Review of Economic Studies, Oxford University Press, vol. 25(2), pages 65-86.
    11. Jules Binsbergen & Michael Brandt, 2007. "Solving dynamic portfolio choice problems by recursing on optimized portfolio weights or on the value function?," Computational Economics, Springer;Society for Computational Economics, vol. 29(3), pages 355-367, May.
    12. Suleyman Basak & Georgy Chabakauri, 2010. "Dynamic Mean-Variance Asset Allocation," Review of Financial Studies, Society for Financial Studies, vol. 23(8), pages 2970-3016, August.
    13. Celikyurt, U. & Ozekici, S., 2007. "Multiperiod portfolio optimization models in stochastic markets using the mean-variance approach," European Journal of Operational Research, Elsevier, vol. 179(1), pages 186-202, May.
    14. Frahm, Gabriel & Memmel, Christoph, 2010. "Dominating estimators for minimum-variance portfolios," Journal of Econometrics, Elsevier, vol. 159(2), pages 289-302, December.
    15. Michael W. Brandt & Pedro Santa-Clara, 2006. "Dynamic Portfolio Selection by Augmentingthe Asset Space," Journal of Finance, American Finance Association, vol. 61(5), pages 2187-2217, October.
    16. Bollerslev, Tim & Engle, Robert F & Wooldridge, Jeffrey M, 1988. "A Capital Asset Pricing Model with Time-Varying Covariances," Journal of Political Economy, University of Chicago Press, vol. 96(1), pages 116-131, February.
    17. Jorion, Philippe, 1986. "Bayes-Stein Estimation for Portfolio Analysis," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 21(03), pages 279-292, September.
    18. Harry Markowitz, 1952. "Portfolio Selection," Journal of Finance, American Finance Association, vol. 7(1), pages 77-91, March.
    19. Leippold, Markus & Trojani, Fabio & Vanini, Paolo, 2004. "A geometric approach to multiperiod mean variance optimization of assets and liabilities," Journal of Economic Dynamics and Control, Elsevier, vol. 28(6), pages 1079-1113, March.
    20. Okhrin, Yarema & Schmid, Wolfgang, 2006. "Distributional properties of portfolio weights," Journal of Econometrics, Elsevier, vol. 134(1), pages 235-256, September.
    21. Paul A. Samuelson, 2011. "Lifetime Portfolio Selection by Dynamic Stochastic Programming," World Scientific Book Chapters,in: THE KELLY CAPITAL GROWTH INVESTMENT CRITERION THEORY and PRACTICE, chapter 31, pages 465-472 World Scientific Publishing Co. Pte. Ltd..
    22. Campbell, John Y. & Viceira, Luis M., 2002. "Strategic Asset Allocation: Portfolio Choice for Long-Term Investors," OUP Catalogue, Oxford University Press, number 9780198296942.
    23. Campbell Harvey & John Liechty & Merrill Liechty & Peter Muller, 2010. "Portfolio selection with higher moments," Quantitative Finance, Taylor & Francis Journals, vol. 10(5), pages 469-485.
    24. Golosnoy, Vasyl & Ragulin, Sergiy & Schmid, Wolfgang, 2011. "CUSUM control charts for monitoring optimal portfolio weights," Computational Statistics & Data Analysis, Elsevier, vol. 55(11), pages 2991-3009, November.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Fügenschuh, Armin, 2009. "Solving a school bus scheduling problem with integer programming," European Journal of Operational Research, Elsevier, vol. 193(3), pages 867-884, March.
    2. Nicola Bianchessi & Michael Drexl & Stefan Irnich, 2017. "The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints," Working Papers 1706, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    3. Christian Tilk & Michael Drexl & Stefan Irnich, 2018. "Nested Branch-and-Price-and-Cut for Vehicle Routing Problems with Multiple Resource Interdependencies," Working Papers 1801, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    4. Nicola Bianchessi & Stefan Irnich, 2016. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Working Papers 1620, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    More about this item


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:69:y:1997:i:0:p:277-297:10.1023/a:1018989130169. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla) or (Rebekah McClure). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.