Push Notification even when app is killed

I have a service which sends notifications that are scheduled in the onStartCommand() method. I want it to send the notifications from the background, even when the application is closed. What I have managed to do is sending notifications when the app is open and also when the app is in the background. However when I click android's overview button and swipe on the app to close it, the notifications aren't send anymore.

Here is the code for the Service:

@Override
public int onStartCommand(Intent intent, int flags, int startId) {
    super.onStartCommand(intent, flags, startId);

    Log.d("NotificationService", "onStartCommand");

    setupNotificationTimers();

    return START_STICKY;
}

setupNotificationTimers() runs below code, which makes sure to run postNotification() at the required date.

Timer timer = new Timer();
long delay = notificationDate.getTime() - currentTime.getTime(); // how much time until notification should be sent

TimerTask timerTask = new TimerTask() {
    public void run() {
        handler.post(() -> postNotification(channel, "title", "content"));
    }
};

timer.schedule(timerTask, delay);

And finally here is my postNotification method:

private void postNotification(int channelIndex, String title, String content) {
    Log.d("NotificationService", "Posting notification...");
    Intent notificationIntent = new Intent(this, MainActivity.class);

    PendingIntent intent = PendingIntent.getActivity(this, 0,
            notificationIntent, PendingIntent.FLAG_CANCEL_CURRENT);

    NotificationCompat.Builder builder = new NotificationCompat.Builder(this, notificationChannelId)
            .setSmallIcon(R.drawable.ic_note)
            .setContentTitle(title)
            .setContentText(content)
            .setAutoCancel(true)
            .setPriority(NotificationCompat.PRIORITY_DEFAULT)
            .setContentIntent(intent);

    notificationManager.notify(channelIndex, builder.build());
}

Most of the solutions I've found don't work for me - for example return START_STICKY; in onStartCommand().

Also when closing app via the overview button my onDestroy() method isn't called. I have no idea why but it makes me unable to restart the service when it's destroyed

@Override
public void onDestroy() {
    Log.d("NotificationService", "Notification service destroyed"); // doesn't get logged
    stoptimers();
    super.onDestroy();
}

How can I make service run even when the app is killed?

EDIT:

Here are the defined services and activities in the AndroidManifest.xml:

<service
    android:name=".NotificationService"
    android:label="@string/app_name">
    <intent-filter>
        <action android:name="your.app.domain.NotificationService" />
        <category android:name="android.intent.category.DEFAULT" />
    </intent-filter>
</service>

<activity android:name=".MainActivity">
    <intent-filter>
        <action android:name="android.intent.action.MAIN" />
        <category android:name="android.intent.category.LAUNCHER" />
    </intent-filter>
</activity>