Scheduling with Variable Time Slot Costs

In this article. we study a class of new scheduling models where time slot costs have to be taken into consideration. In Such models, processing a job will incur certain cost which is determined by the time slots occupied by the job in a schedule. The models apply when operational costs vary over time. The objective of the scheduling models is to minimize the total time slot costs plus a traditional scheduling performance measure. We consider the following performance measures: total completion time, maximum lateness/tardiness, total weighted number of tardy jobs, and total tardiness. We prove the intractability of the models under general parameters and provide polynomial-time algorithms for special cases with non-increasing time slot costs. (C) 2010 Wiley Periodicals. Inc. Naval Research Logistics 57: 159-171, 2010