Advertising is the primary source of revenue for newspaper companies. Over the past 10 to 15 years, the newspaper industry has been adjusting to changes in the mix of services that produce this revenue. The two main categories of services are run on press (ROP) advertising and preprinted insert advertising. ROP advertising is printed in the newspaper during the live press run each night, whereas preprinted inserts are produced (usually at a commercial printing facility) before the nightly production run and inserted into or delivered with the newspaper. Preprinted inserts offer several advantages for advertisers. Different sizes and quality of paper stock can be used to make ads unique and more colorful than possible on a newspaper printing press. Also, advertisers can tightly control quality for preprinted inserts unlike newspaper quality that varies widely.

Although revenue has been increasing in both categories of advertising, revenue from preprinted inserts has been growing at a higher rate than ROP advertising. For many newspaper companies, this shift in revenue mix has created scheduling challenges in the production area. With inserts, advertisers can select the zones to which specific sets of advertisements are distributed. A zone is a distinct geographical area where all the papers delivered in the area receive the same set of advertising inserts. The challenge for newspaper companies is to schedule the production run to process the correct combination of inserts for all the different zones and complete the run early enough to get the papers to the circulation department (and readers) on time. For many papers, the problem is exacerbated by advertisers' desires to "micro-zone" or have more zones of smaller size, increasing the specificity with which different groups of consumers can be targeted.

Art Carter is the production manager for a medium-sized newspaper company. Each night, he and his employees must design a schedule for combining the appropriate advertising inserts for 36 different delivery zones into the newspaper. Art's company owns four inserting machines that can each be loaded with the inserts for a particular zone. Two of the inserting machines operate at a rate of 12,000 papers per hour, whereas the other two machines operate at a rate of 11,000 per hour. The equipment inserts the loaded set of inserts into newspapers coming off the production press until all the papers for a particular zone are completed.

When the inserts for a particular zone are completed, the inserting machine is stopped and reloaded with the inserts for the next zone. This reloading (or changeover) process takes different amounts of time depending on how much work is required to load the machine with the next zone's set of inserts. The zones can be processed in any order and on any of the four inserting machines. However, all the advertising for a particular zone must be processed on the same inserting machine (that is, the inserts for a single zone are not distributed across multiple inserting machines).

The file NewspaperData.xlsx that accompanies this book contains sample data for a typical night's inserting workload for this company. In particular, this file contains the quantity of newspapers being produced for each of the 36 delivery zones and the estimated changeover times required to switch from one zone's set of inserts to another zone. Art has asked you to develop a model to design an optimal production schedule for the inserting equipment. In particular, he wants to determine which zones should be assigned to each of the four machines and the optimal order for processing the jobs assigned to each machine. His objective is to minimize the amount of time is takes (start to finish) to complete all the newspapers.