Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

Mokotoff, E.; Jimeno, J. L.
November 2002
Annals of Operations Research;Nov2002, Vol. 117 Issue 1-4, p133
Academic Journal
The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.


Related Articles

  • Makespan minimization of a flowshop sequence-dependent group scheduling problem. Salmasi, Nasser; Logendran, Rasaratnam; Skandari, Mohammad // International Journal of Advanced Manufacturing Technology;Sep2011, Vol. 56 Issue 5-8, p699 

    The flowshop sequence dependent group scheduling problem with minimization of makespan as the objective ( F|fmls, S, prmu| C) is considered in this paper. It is assumed that several groups with different number of jobs are assigned to a flow shop cell that has m machines. The goal is to find the...

  • A NOTE ON "LEVEL SCHEDULES FOR MIXED-MODEL ASSEMBLY LINES IN JUST-IN-TIME PRODUCTION SYSTEMS". Kubiak, Wieslaw; Sethi, Suresh // Management Science;Jan1991, Vol. 37 Issue 1, p121 

    This note formulates an assignment problem for obtaining optimal level schedules for mixed-model assembly lines in JIT production systems. The problem was formulated as a quadratic integer programming problem in a recent paper by Miltenburg (1989) where, however, only enumerative algorithms and...

  • An integer programming approach to elective surgery scheduling. Marques, Inês; Captivo, M.; Vaz Pato, Margarida // OR Spectrum;Apr2012, Vol. 34 Issue 2, p407 

    The scope of this work covers a real case of elective surgery planning in a Lisbon hospital. The aim is to employ more efficiently the resources installed in the surgical suite of the hospital in question besides improving the functioning of its surgical service. Such a planning sets out to...

  • A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem. Hadjar, Ahmed; Marcotte, Odile; Soumis, François // Operations Research;Jan/Feb2006, Vol. 54 Issue 1, p130 

    We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving it that combines column generation, variable fixing, and cutting planes. We show that the solutions of the linear relaxation of the MDVSP contain many "odd cycles." We derive a...

  • Models and algorithms for a staff scheduling problem. Caprara, Alberto; Monaci, Michele; Toth, Paolo // Mathematical Programming;Sep2003, Vol. 98 Issue 1-3, p445 

    Presents mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. Steps in solving staff scheduling problems; Formal definition of the problem; Information on the minimum number of employees and the associated pattern for each...

  • EXTREME POINT MATHEMATICAL PROGRAMMING. Kirby, M. J. L.; Love, H. R.; Swarup, Kanti // Management Science;May72, Vol. 18 Issue 9, p540 

    The paper considers a class of optimization problems. The problems are linear programming problems: maximize ex subject to Ax = b with the additional constraint that x must also be an extreme point of a second convex polyhedron Dx = d. X ≥ 0. A cutting-plane algorithm for solving such...

  • Mathematical model for cyclic scheduling with work-in-process minimization. Ben Amar, Mohamed; Camus, Hervé; Bourdeaud'huy, Thomas; Korbaa, Ouajdi // Flexible Services & Manufacturing Journal;Jun2011, Vol. 23 Issue 2, p111 

    This paper is part of an original approach of mathematical modeling for solving cyclic scheduling problems. More precisely, we consider the cyclic job shop. This kind of manufacturing systems is well fitted to medium and large production demands. Many methods have been proposed to solve the...

  • Two-Machine Flow-Shop Scheduling with Job Delivery Coordination. Jen-Shiang Chen // Open Operational Research Journal;2011, Vol. 5, p1 

    This study considers a class of two-machine flow-shop scheduling problems with job delivery coordination. Both vehicle capacity and transportation times are also investigated. The objective is to minimize the mean arrival time of jobs. Two integer programming models are developed to optimally...

  • Synthetical Evaluation Model Based on Integer Programming for Arranging Single Round Robin Schedule. Jiguo Dong; Jianping Cai // Advanced Materials Research;2014, Issue 889-890, p1203 

    In this paper, the synthetical evaluation model based on integer programming for arrangement of single round robin schedule is established through analyzing the major factors of matches. Following, as an example, we analysis and evaluate the schedule of NBA 08-09 season according to this...


Read the Article


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

Try another library?
Sign out of this library

Other Topics