In this paper, an agent-based search model of the labor market with heterogeneous agents and an on-the-job search is developed, i.e. the long-term unemployed and other job seekers compete for vacancies which differ in skills demands and in the sector of the economy. Job placement agencies help both types of unemployed persons find the proper vacant job by improving their search effectiveness and by sharing leveraged job advertisements. The agents' interactions take place in an artificial world drawn from labor market search theory. Six global model parameters were calibrated with the Latin hypercube sampling technique for one of the largest urban areas in Poland. To investigate the impact of parameters on model output, two global sensitivity analysis methods were used, i.e. Morris screening and Sobol indices. The results show that both programs considerably influence unemployment and long-term unemployment ratios as well as the level of wages, duration of unemployment, skills demand and worker turnover. Moreover, strong cross-effects were detected: programs aimed at one group of job seekers affect other job seekers and the whole economy. This impact is sometimes positive and sometimes it is negative.