Alarms get lost when cell phone is turned off and on!

Since turning off the device alarms are lost, you must create them again at the time the device is restarted.

Android launches an Intent ( android.intent.action.BOOT_COMPLETED ) when the restart is finished. Take advantage of this and register a BroadcastReceiver to execute code when this occurs.

Declare BroadcastReceiver in AndroidManifest.xml

<receiver android:name="aSuaPackage.StartUpBootReceiver">
    <intent-filter>
        <action android:name="android.intent.action.BOOT_COMPLETED" />
    </intent-filter>
</receiver>  

Add the permission:

<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />

Type the BroadcastReceiver class:

public class StartUpBootReceiver extends BroadcastReceiver {

    @Override
    public void onReceive(Context context, Intent intent) {

        if (Intent.ACTION_BOOT_COMPLETED.equals(intent.getAction())) {

            // Crie aqui o alarme.
        }
    }
}  

Note:
How the receiver was declared is enabled and will run whenever the device is restarted. It can be declared "disabled", using android:enabled="false" , as follows:

<receiver android:name="aSuaPackage.StartUpBootReceiver"
          android:enabled="false">
    <intent-filter>
        <action android:name="android.intent.action.BOOT_COMPLETED" />
    </intent-filter>
</receiver>  

You can "turn it on" after this:

ComponentName receiver = new ComponentName(context, SampleBootReceiver.class);
PackageManager pm = context.getPackageManager();

pm.setComponentEnabledSetting(receiver,
        PackageManager.COMPONENT_ENABLED_STATE_ENABLED,
        PackageManager.DONT_KILL_APP);

You can later "disable" it like this:

ComponentName receiver = new ComponentName(context, SampleBootReceiver.class);
PackageManager pm = context.getPackageManager();

pm.setComponentEnabledSetting(receiver,
        PackageManager.COMPONENT_ENABLED_STATE_DISABLED,
        PackageManager.DONT_KILL_APP);

For more information, see the Scheduling Repeating Alarms guide.

Make a receiver for the action ACTION_BOOT_COMPLETED, and then you can reconfigure some action you want when the device is turned off / on.

Just to complement the answer

Add the following permissions:

<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED”/>

Configure your receiver:

<receiver android:name=“.MeuReceiver"
    android:enabled="true"
    android:permission="android.permission.ACTION_BOOT_COMPLETED">
    <intent-filter>
        <action android:name="android.intent.action.BOOT_COMPLETED"></action>
        <category android:name="android.intent.category.DEFAULT" />
    </intent-filter>
</receiver>