Scheduling projects with labor constraints.

*(English)*Zbl 0984.90012Summary: We consider a Labor Constrained Scheduling Problem (LCSP), which is a simplification of a practical problem arising in industry. Jobs are subject to precedence constraints and have specified processing times. Moreover, for each job the labor requirement varies as the job is processed. Given the amount of labor available in each period, the problem is to finish all the jobs as soon as possible, that is, to minimize the makespan, subject to the precedence and labor constraints. Several Integer Programming (IP) formulations for this problem are discussed, and valid inequalities for these different models are introduced.

It turns out that a major drawback in using an IP approach is the weakness of the lower bound relaxations. However, we report computational experiments showing how the solution of the linear relaxation of the IP models can be used to provide good schedules. Solutions arising from these LP-based heuristics are considerably improved by local search procedures. We further exploit the capabilities of local search for LCSP by designing a tabu search algorithm. The computational experiments on a benchmark data set show that tabu search algorithm generates the best-known upper bounds for almost all these instances. We also show how IP can be used to provide reasonably good lower bounds for LCSP when the makespan is replaced by suitably modified objective functions. Finally, some directions for further investigations, which may turn IP techniques into a more interesting tool for solving such a problem, are suggested.

It turns out that a major drawback in using an IP approach is the weakness of the lower bound relaxations. However, we report computational experiments showing how the solution of the linear relaxation of the IP models can be used to provide good schedules. Solutions arising from these LP-based heuristics are considerably improved by local search procedures. We further exploit the capabilities of local search for LCSP by designing a tabu search algorithm. The computational experiments on a benchmark data set show that tabu search algorithm generates the best-known upper bounds for almost all these instances. We also show how IP can be used to provide reasonably good lower bounds for LCSP when the makespan is replaced by suitably modified objective functions. Finally, some directions for further investigations, which may turn IP techniques into a more interesting tool for solving such a problem, are suggested.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C10 | Integer programming |

90B40 | Search theory |

##### Keywords:

branch-and-prune algorithm; LP-based ordering heuristics; labor constrained scheduling problem; integer programming; linear relaxation; local search; tabu search algorithm
PDF
BibTeX
XML
Cite

\textit{C. C. B. Cavalcante} et al., Discrete Appl. Math. 112, No. 1--3, 27--52 (2001; Zbl 0984.90012)

Full Text:
DOI

##### References:

[1] | Aarts, E.; Lenstra, J.K., Local search in combinatorial optimization, (1997), Wiley Chichester · Zbl 0869.00019 |

[2] | G. Andreatta, L. Brunetta, G. Guastalla, From ground holding to free flight: a new exact approach. Technical Report, Department of Pure and Applied Mathematics, University of Padova, Italy, 1988. · Zbl 1014.90015 |

[3] | Baker, K.R., Introduction to sequencing and scheduling, (1974), Wiley New York |

[4] | C.C.M.B. Cavalcante, Escalonamento com restrição de mão-de-obra: heurı́sticas combinatórias e limitantes inferiores, M.Sc. Dissertation, Instituto de Computação. Universidade Estadual de Campinas (UNICAMP), SP, Brazil. 1998, (in Portuguese). |

[5] | S. Heipcke, Y. Colombani, C.C.B.M. Cavalcante, C. C. de Souza, Scheduling under labour resource constraints, Constraints 5 (2000) 415-422. · Zbl 0972.68502 |

[6] | Glover, F., Tabu search – part I, ORSA J. comput., 1, 190-206, (1989) · Zbl 0753.90054 |

[7] | Glover, F., Tabu search – part II, ORSA J. comput., 2, 4-32, (1990) · Zbl 0771.90084 |

[8] | Glover, F.; Laguna, M., Tabu search, (), 70-150 |

[9] | M.X. Goemans, Improved approximation algorithms for scheduling with release dates, Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 591-598. · Zbl 1321.68502 |

[10] | Gröflin, H.; Liebling, T., Connected and alternating vectors: polyhedra and algorithms, Math. programming, 20, 233-244, (1981) · Zbl 0448.90035 |

[11] | S. Heipcke, Resource constrained job-shop scheduling with constraint nets – two case studies, Diploma Thesis, Mathematisch Geographische Fakultaet, Katholische Universitaet Eichstaett, 1995. |

[12] | S. Heipcke, Y. Colombani, A new constraint programming approach to large scale resource constrained scheduling, Workshop on Models and Algorithms for Planning and Scheduling Problems, Cambridge, UK, 1997. |

[13] | S. Heipcke, Y. Colombani, Solving RCPSPs with SchedEns-Work-in-Progress Report, School of Business, University of Buckingham, 1997. |

[15] | Nemhauser, G.L.; Savelsbergh, M.W.P.; Sigismondi, G.C., MINTO, a mixed integer optimizer, Oper. res. lett., 15, 47-58, (1994) · Zbl 0806.90095 |

[16] | Patterson, J.H., A comparison of exact approaches for solving the multiple constrained resource project scheduling problem, Manage. sci., 30, 854-867, (1984) |

[17] | Pritsker, A.A.B; Watters, L.J.; Wolfe, P.M., Multiproject scheduling with limited resources: a zero-one programming approach, Manage. sci., 16, 93-99, (1969) |

[18] | Rayward-Smith, V.J.; Osman, I.H.; Reeves, C.R.; Smith, G.D., Modern heuristic search methods, (1996), Wiley New York · Zbl 0942.90004 |

[19] | Reeves, C., Modern heuristic techniques for combinatorial problems, (1993), Wiley New York · Zbl 0942.90500 |

[20] | M.W.P. Savelsbergh, R.N. Uma, J. Wein, An experimental study of LP-based approximation algorithms for scheduling problems, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 453-462. · Zbl 0938.68534 |

[21] | A. Schulz, M. Skutella, Scheduling LPs bear probabilities: randomized approximations for min-sum criteria, Proceedings of the 1997 European Symposium on Algorithms, 1997, pp. 416-429. |

[22] | Sousa, J.; Wolsey, L.A., Time-indexed formulations of non-preemptive single machine scheduling problems, Math. programming, 54, 353-367, (1992) · Zbl 0768.90041 |

[23] | M. van den Akker, LP-based solution methods for single-machine scheduling problems, Ph.D. Thesis, Technical University of Eindhoven, 1994. · Zbl 0828.90059 |

[24] | M. van den Akker, C.A.J. Hurkens, M.W.P. Savelsbergh, Time-indexed formulations for machine scheduling problems: column generation, INFORMS J. on Computing 12 (2000) 111-124. · Zbl 1034.90004 |

[25] | H.M. Wagner, Principles of Operations Research, Prentice-Hall, Englewood Cliffs, Exercise 50, 1969, p. 502. · Zbl 0193.18402 |

[26] | Wolsey, L.A., MIP modelling of changeovers in production planning and scheduling problems, European J. oper. res., 99, 154-165, (1997) · Zbl 0923.90088 |

[27] | Wolsey, L.A., Integer programming, (1998), Wiley New York · Zbl 0299.90012 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.