Presenter: Dr. Kan Fang, postdoctoral researcher

We study scheduling as a means to address the increasing concerns related to energy consumption and electricity cost in manufacturing enterprises. In particular, we consider minimizing the total electricity cost on a single machine under time-of-use tariffs (the SMSEC problem for short), in which we incorporate the technology of dynamic speed scaling and the variable pricing of electricity into these problems to improve energy efficiency in manufacturing.

We consider both uniform-speed and speed-scalable machine environments. For the uniform-speed case, we prove that this problem is strongly NP-hard, and in fact inapproximable within a constant factor, unless P=NP. For the speed-scalable case, in which jobs can be processed at an arbitrary speed with a trade-off between speed and energy consumption, we show that this problem is strongly NP-hard. We also present different approximation algorithms for this case and test the computational performance of these approximation algorithms on randomly generated instances.
<!--[endif]-->