Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem

被引：26

作者：

Darby-Dowman K. ^{[1
]}

Little J. ^{[1
]}

Mitra G. ^{[1
]}

Zaffalon M. ^{[2
]}

机构：

[1] Department of Mathematics and Statistics, Brunel University, Uxbridge, Middlesex

[2] Universitá degli Studi di Milano, Dip. di Matematica, 20129, Milan

来源：

Constraints | 1997年 / 1卷 / 3期

关键词：

Constraint logic programming; Generalised assignment problem; Integer programming; Optimisation;

D O I：

10.1007/BF00137871

中图分类号：

学科分类号：

摘要：

Generalised Assignment Problems (GAP), traditionally solved by Integer Programming techniques, are addressed in the light of current Constraint Programming methods. A scheduling application from manufacturing, based on a modified GAP, is used to examine the performance of each technique under a variety of problem characteristics. Experimental evidence showed that, for a set of assignment problems, Constraint Logic Programming (CLP) performed consistently better than Integer Programming (IP). Analysis of the CLP and IP processes identified ways in which the search was effective. The insight gained from the analysis led to an Integer Programming approach with significantly improved performance. Finally, the issue of collaboration between the two contrasting approaches is examined with respect to ways in which the solvers can be combined in an effective manner. © 1997 Kluwer Academic Publishers.

引用

页码：245 / 264

页数：19

共 22 条

[1]

Bellone J., Chamard A., Pradelles C., Plane': An evolutive planning system for aircraft production written in CHIP, Proceedings of the Practical Applications of Prolog Conference, (1992)

[2]

250-118 Data Sets of Workforce Management Scheduling Problem

[3]

11 Data Sets for the Frequency Assignment Problem

[4]

Version 4.0 of Using the CPLEX Callable Library and CPLEX Mixed Integer Library, (1995)

[5]

Crowder H.P., Dembo R.S., Mulvey J.M., Reporting mathematical experiments in mathematical programming, Mathematical Programming, 15, pp. 316-329, (1978)

[6]

Dincbas M., Simonis H., APACHE - A constraint based automated stand allocation system, Proceedings of the Advanced Software Technology in Air Transport Conference, pp. 267-282, (1991)

[7]

Duncan T., Schedule IT: Experiences with a constraint based approach to building an intelligent vehicle scheduling system, Constraint Handling Techniques Seminar, (1994)

[8]

El-Sakkout, Modelling fleet assignment in a flexible environment, Proceedings of the Second International Conference on the Practical Application of Constraint Technology (PACT 96), pp. 27-39, (1995)

[9]

ECLiPSe User Guide, (1994)

[10]

Fisher M., Jaikumar R., A generalized assignment heuristic for the large scale vehicle routing problem, Networks, 11, 2, pp. 109-124, (1981)

← 1 2 3 →