Attribute charts are used widely for monitoring binary events in manufacturing, service, and healthcare processes. While Shewhart type charts are efficacious in detecting large or sudden shifts in a nonconforming rate p, exponentially weighted moving average (EWMA) type charts tend to be more powerful for detecting smaller or gradual shifts. Since many processes can shift by various amounts, this paper proposes a combined optimized Shewhart-EWMA dual chart that combines the strengths of both charts to quickly detect shifts of any random magnitude within a defined range. The performance of this combined Shewhart-EWMA chart is optimized by allocating total detection power between the Shewhart chart element and EWMA chart element in a manner that yields the best overall effectiveness while maintaining the false alarm rate at a specified desired level. In numeric analysis under a range of settings, the detection speed of this combined Shewhart-EWMA chart is found to outperform individual Shewhart and EWMA charts, with up to 499% and 31% fewer average number of defective items respectively until process shifts of random sizes are detected. It also demonstrates enhanced overall efficacy when compared to synthetic, cumulative sum, combined Shewhart-synthetic, and combined Shewhart-CUSUM charts.