Firebase FCM not calling service when app is in background/killed

Question

I am integrating firebase FCM push notifications on an android app and all things are working fine except when app goes background/killed, the MyFirebaseMessagingService is not called. It works fine when app is in foreground. The onMessageReceived() is not at all called when app is in background. I want to send push notifications from Firebase console UI only to all subscribers at once, not trying to do 1-1 messaging or sending through web server. Not that the service is not running when app is closed from Recent Apps tray, the app is not at all working when simply the app goes to background.

Below are the respective codes:

MyFirebaseMessagingService

public class MyFirebaseMessagingService extends FirebaseMessagingService {

private static final String TAG = "MyFirebaseMsgService";

/**
 * Called when message is received.
 *
 * @param remoteMessage Object representing the message received from Firebase Cloud Messaging.
 */
// [START receive_message]



@Override
public void onMessageReceived(RemoteMessage remoteMessage) {
    // TODO(developer): Handle FCM messages here.
    // Not getting messages here? See why this may be:
    Log.d(TAG, "From: " + remoteMessage.getFrom());

    // Check if message contains a data payload.
    if (remoteMessage.getData().size() > 0) {
        Log.d(TAG, "Message data payload: " + remoteMessage.getData());

        if (/* Check if data needs to be processed by long running job */ true) {
            // For long-running tasks (10 seconds or more) use Firebase Job Dispatcher.
            scheduleJob();
        } else {
            // Handle message within 10 seconds
            handleNow();
        }

    }

    // Check if message contains a notification payload.
    if (remoteMessage.getNotification() != null) {
        Log.d(TAG, "Message Notification Body: " + remoteMessage.getNotification().getBody());
    }

    // Also if you intend on generating your own notifications as a result of a received FCM
    // message, here is where that should be initiated. See sendNotification method below.
}

Service Declaration in Manifest

<service android:name=".MyFirebaseMessagingService">
    <intent-filter>
        <action android:name="com.google.firebase.MESSAGING_EVENT" />
    </intent-filter>
</service>

Application Class Declaration

FirebaseMessaging.getInstance().subscribeToTopic("weather")
            .addOnCompleteListener(new OnCompleteListener<Void>() {
                @Override
                public void onComplete(@NonNull Task<Void> task) {
                    String msg = "Subscribed";
                    if (!task.isSuccessful()) {
                        msg = "Message";
                    }
                    Log.d("Token", msg);
                    Toast.makeText(getApplicationContext(), msg, Toast.LENGTH_SHORT).show();
                }
            });