@article{6512, abstract = {{Scheduling problems are essential for decision making in many academic disciplines, including operations management, computer science, and information systems. Since many scheduling problems are NP-hard in the strong sense, there is only limited research on exact algorithms and how their efficiency scales when implemented on parallel computing architectures. We address this gap by (1) adapting an exact branch-and-price algorithm to a parallel machine scheduling problem on unrelated machines with sequence- and machine-dependent setup times, (2) parallelizing the adapted algorithm by implementing a distributed-memory parallelization with a master/worker approach, and (3) conducting extensive computational experiments using up to 960 MPI processes on a modern high performance computing cluster. With our experiments, we show that the efficiency of our parallelization approach can lead to superlinear speedup but can vary substantially between instances. We further show that the wall time of serial execution can be substantially reduced through our parallelization, in some cases from 94 hours to less than six minutes when our algorithm is executed on 960 processes.}}, author = {{Rauchecker, Gerhard and Schryen, Guido}}, journal = {{Computers & Operations Research}}, keywords = {{parallel machine scheduling with setup times, parallel branch-and-price algorithm, high performance computing, master/worker parallelization}}, number = {{104}}, pages = {{338--357}}, publisher = {{Elsevier}}, title = {{{Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm}}}, year = {{2019}}, } @inproceedings{5678, abstract = {{Many academic disciplines - including information systems, computer science, and operations management - face scheduling problems as important decision making tasks. Since many scheduling problems are NP-hard in the strong sense, there is a need for developing solution heuristics. For scheduling problems with setup times on unrelated parallel machines, there is limited research on solution methods and to the best of our knowledge, parallel computer architectures have not yet been taken advantage of. We address this gap by proposing and implementing a new solution heuristic and by testing different parallelization strategies. In our computational experiments, we show that our heuristic calculates near-optimal solutions even for large instances and that computing time can be reduced substantially by our parallelization approach.}}, author = {{Rauchecker, Gerhard and Schryen, Guido}}, booktitle = {{Australasian Conference on Information Systems}}, keywords = {{scheduling, decision support, heuristic, high performance computing, parallel algorithms}}, pages = {{1--13}}, title = {{{High-Performance Computing for Scheduling Decision Support: A Parallel Depth-First Search Heuristic}}}, year = {{2015}}, } @inproceedings{1998, abstract = {{Nearly all existing HPC systems are operated by resource management systems based on the queuing approach. With the increasing acceptance of grid middleware like Globus, new requirements for the underlying local resource management systems arise. Features like advanced reservation or quality of service are needed to implement high level functions like co-allocation. However it is difficult to realize these features with a resource management system based on the queuing concept since it considers only the present resource usage. In this paper we present an approach which closes this gap. By assigning start times to each resource request, a complete schedule is planned. Advanced reservations are now easily possible. Based on this planning approach functions like diffuse requests, automatic duration extension, or service level agreements are described. We think they are useful to increase the usability, acceptance and performance of HPC machines. In the second part of this paper we present a planning based resource management system which already covers some of the mentioned features.}}, author = {{Hovestadt, Matthias and Kao, Odej and Keller, Axel and Streit, Achim}}, booktitle = {{Proc. Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP)}}, keywords = {{High Performance Computing, Service Level Agreement, Grid Resource, Resource Management System, Advance Reservation}}, pages = {{1--20}}, title = {{{Scheduling in HPC Resource Management Systems: Queuing vs. Planning}}}, doi = {{10.1007/10968987_1}}, volume = {{2862}}, year = {{2003}}, } @inproceedings{2418, abstract = {{ This paper presents TKDM, a PC-based high-performance reconfigurable computing environment. The TKDM hardware consists of an FPGA module that uses the DIMM (dual inline memory module) bus for high-bandwidth and low-latency communication with the host CPU. The system's firmware is integrated with the Linux host operating system and offers functions for data communication and FPGA reconfiguration. The intended use of TKDM is that of a dynamically reconfigurable co-processor for data streaming applications. The system's firmware can be customized for specific application domains to facilitate simple and easy-to-use programming interfaces. }}, author = {{Plessl, Christian and Platzner, Marco}}, booktitle = {{Proc. Int. Conf. on Field Programmable Technology (ICFPT)}}, keywords = {{coprocessor, DIMM, memory bus, FPGA, high performance computing}}, pages = {{252--259}}, publisher = {{IEEE Computer Society}}, title = {{{TKDM – A Reconfigurable Co-processor in a PC's Memory Slot}}}, doi = {{10.1109/FPT.2003.1275755}}, year = {{2003}}, }