Open Access. Powered by Scholars. Published by Universities.®

Operations Research, Systems Engineering and Industrial Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Series

Artificial Intelligence and Robotics

1996

Articles 1 - 2 of 2

Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering

Combinatorial Approaches For Hard Problems In Manpower Scheduling, Hoong Chuin Lau Jan 1996

Combinatorial Approaches For Hard Problems In Manpower Scheduling, Hoong Chuin Lau

Research Collection School Of Information Systems

Manpower scheduling is concerned with the construction of a workers' schedule which meets demands while satisfying given constraints. We consider a manpower scheduling Problem, called the Change Shift Assignment Problem(CSAP). In previous work, we proved that CSAP is NP-hard and presented greedy methods to solve some restricted versions. In this paper, we present combinatorial algorithms to solve more general and realistic versions of CSAP which are unlikely solvable by greedy methods. First, we model CSAP as a fixed-charge network and show that a feasible schedule can be obtained by finding disjoint paths in the network, which can be derived ...


Randomized Approximation Of The Constraint Satisfaction Problem, Hoong Chuin Lau, Osamu Watanabe Jan 1996

Randomized Approximation Of The Constraint Satisfaction Problem, Hoong Chuin Lau, Osamu Watanabe

Research Collection School Of Information Systems

We consider the Weighted Constraint Satisfaction Problem (W-CSP) which is a fundamental problem in Artificial Intelligence and a generalization of important combinatorial problems such as MAX CUT and MAX SAT. In this paper, we prove non-approximability properties of W-CSP and give improved approximations of W-CSP via randomized rounding of linear programming and semidefinite programming relaxations. Our algorithms are simple to implement and experiments show that they are run-time efficient.