Nowadays the successful operation of a company is unimaginable without fast and reliable
communication. As a result, so-called Communication Service Providers play an important
role in today’s business life. Their orders have to be carried out promptly and dependably,
let them be requests for new installations, modifications, or maintenance tasks. These
orders have to be performed at different locations and they often have deadlines or
strict starting times. Violating such a timing requirement usually implies penalties.
In this paper, scheduling problems arising at a Hungarian service provider are examined.
At this company, orders are decomposed into smaller tasks, which can be performed
by specially trained personnel. Transportation of these specialists contributes a
lot to the costs and to the complexity of their scheduling, as well. The goal is to
minimize the overall cost of satisfying all orders within the given time horizon with
the available assets of the company. The proposed approach relies on the S-graph framework,
which has been applied to various production scheduling problems in the literature.
In addition to an unambiguous and sound S-graph model of the examined problem, slight
modifications of the scheduling algorithms for cost minimization, and new bounding
methods have been developed. Several of such bounds have been provided and tested
for performance and scalability over a large number of generated examples. The sensitivity
of the approach for certain problem features has also been examined.