Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
A Tabu Search Algorithm To Minimize The Makespan For The Unrelated Parallel Machines Scheduling Problem With Setup Times, Magdy Helal, Ghaith Rabadi, Ameer Al-Salem
A Tabu Search Algorithm To Minimize The Makespan For The Unrelated Parallel Machines Scheduling Problem With Setup Times, Magdy Helal, Ghaith Rabadi, Ameer Al-Salem
Engineering Management & Systems Engineering Faculty Publications
In this paper we propose a tabu search implementation to solve the unrelated parallel machines scheduling problem with sequence- and machine- dependent setup times to minimize the schedules makespan. The problem is NP-hard and finding an optimal solution efficiently is unlikely. Therefore, heuristic techniques are more appropriate to find near-optimal solutions. The proposed tabu search algorithm uses two phases of perturbation schemes: the intra-machine perturbation, which optimizes the sequence of jobs on the machines, and the inter-machine perturbation, which balances the assignment of the jobs to the machines. We compare the proposed algorithm to an existing one that addressed the …
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
Computer Science Faculty Publications
A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain “local density” characteristics. Typically, the notion of local density is equated with the absence of chordless paths of length three or more. Recently, a new metric for local density has been proposed, allowing a number of such induced paths to occur. More precisely, a graphG is called P4-sparse if no set of five vertices inG induces more than one chordless path of length three. P4-sparse graphs generalize the well-known class of cographs corresponding to …
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu
Computer Science Faculty Publications
The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a minimum path cover for a cograph G. In case G has a Hamiltonian path (cycle) our algorithm exhibits the path (cycle) as well.