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

Maffioli, Francesco; Sciomachen, Anna
January 1997
Annals of Operations Research;1997, Vol. 69 Issue 1-4, p277
Academic Journal
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 problem 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 available MIP software like OSL.


Related Articles

  • An Application of Lagrangian Relaxation to Scheduling in Power-Generation Systems. Muckstadt, John A.; Koenig, Sherri A. // Operations Research;May/Jun77, Vol. 25 Issue 3, p387 

    Two major decisions are made when scheduling the operations of a fossil-fuel power-generating system over a short time horizon. The "unit commitment" decision indicates what generating units are to be in use at each point in time. The "economic dispatch" decision is the allocation of system...

  • A visual interface for model-fitting. Smith, Andrew J.; Malik, Zahid; Nelder, John; Spence, Robert // Quality & Reliability Engineering International;Mar2001, Vol. 17 Issue 2, p85 

    We describe a tool which supports the activity of a human being in fitting a mathematical model to measured or simulated data. The tool offers two principal advantages; its use requires a minimum of statistical knowledge, and its visual and interactive nature ensures that its use is intuitive....

  • An Agent-Based Scheduling Framework for Flexible Manufacturing Systems. Badr, Iman // International Journal of Computer, Information & Systems Science;2008, Vol. 2 Issue 2, p123 

    The concept of flexible manufacturing is highly appealing in gaining a competitive edge in the market by quickly adapting to the changing customer needs. Scheduling jobs on flexible manufacturing systems (FMSs) is a challenging task of managing the available flexibility on the shop floor to...

  • Job-Shop Scheduling Problem With Sequence Dependent Setup Times. Moghaddas, R.; Houshmand, M. // International MultiConference of Engineers & Computer Scientists;2008, p1546 

    The majority of researches on scheduling assume setup times negligible or as a part of the processing time. In this paper, job shop scheduling with sequence dependent setup times is considered. After defining the problem, a mathematical model is developed. Implementing the mathematical model in...

  • A Bayesian Analysis of Very Small Unreplicated Experiments. Aguirre‐Torres, Víctor; Vara, Román // Quality & Reliability Engineering International;Apr2014, Vol. 30 Issue 3, p413 

    It is not uncommon to deal with very small experiments in practice. For example, if the experiment is conducted on the production process, it is likely that only a very few experimental runs will be allowed. If testing involves the destruction of expensive experimental units, we might only have...

  • Distributions of Maximum Likelihood Estimators and Model Comparisons. Hingley, Peter // AIP Conference Proceedings;9/9/2008, Vol. 1045 Issue 1, p111 

    Experimental data need to be assessed for purposes of model identification, estimation of model parameters and consequences of mis-specified model fits. Here the first and third factors are considered via analytic formulations for the distribution of the maximum likelihood estimates. When...

  • THE IMPACT OF PROCESSING TIME KNOWLEDGE ON DYNAMIC JOB-SHOP SCHEDULING. Wein, Lawrence M.; Ou, Jihong // Management Science;Aug1991, Vol. 37 Issue 8, p1002 

    The goal of this paper is to determine if the results for dynamic job-shop scheduling problems are affected by the assumptions made with regard to the processing time distributions and the scheduler's knowledge of the processing times. Three dynamic job-shop scheduling problems (including a...

  • Capacitated lot-sizing and scheduling with sequence-dependent, period-overlapping and non-triangular setups. Menezes, António; Clark, Alistair; Almada-Lobo, Bernardo // Journal of Scheduling;Apr2011, Vol. 14 Issue 2, p209 

    In production planning, sequence dependent setup times and costs are often incurred for switchovers from one product to another. When setup times and costs do not respect the triangular inequality, a situation may occur where the optimal solution includes more than one batch of the same product...

  • Study on job shop scheduling with sequence-dependent setup times using biological immune algorithm. Zhou, Yaqin; Li, Beizhi; Yang, Jianguo // International Journal of Advanced Manufacturing Technology;Aug2006, Vol. 30 Issue 1/2, p105 

    Sequence-dependent setup times are one of the most important factors for the optimization of scheduling the production targets. Usually, they include the changing of tools, fixtures, cutting tools and the cleaning of production equipments. Some of them are relevant not only to the sequence...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics