Document Type : Original Article
Authors
Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran.
Abstract
In this paper, the problem of two-machine flow shop scheduling to minimize total energy costs under time-of-use tariffs is investigated. As the objective function of this study is not a regular measure, allowing intentional idle-time can be advantageous. So this study considers two approaches, one for non-delay version of the problem and the other one for a situation when inserting intentional idle time is permitted. A mixed integer linear programming is formulated to determine the timing of jobs in order to minimize total energy costs while idle time insertion is allowed. For the non-delay version of the problem, a branch-and-bound algorithm is presented. A lower bound and several dominance properties are used to increase the speed of the branch-and-bound algorithm. Computational experiments are also given to evaluate the performance of the algorithm. Based on results, the proposed algorithms can optimally schedule jobs in small size samples but by increasing the number of jobs from 15 and cost periods from 3, the performance of branch-and-bound has been decreased.
Keywords
Aghelinejad, M., Ouazene, Y., and Yalaoui, A., (2016). “Machine and production scheduling under electricity time varying prices”, In Industrial Engineering and Engineering Management (IEEM), IEEE International Conference on, pp. 992-996.
Che, A., Lv, K., Levner, E., and Kats, V., (2015). “Energy consumption minimization for single machine scheduling with bounded maximum tardiness”. In Networking, Sensing and Control (ICNSC), IEEE 12th International Conference on, pp. 146-150.
Che, A., Zeng, Y., and Lyu, K., (2016). “An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs”, Journal of Cleaner Production, Vol. 129, pp. 565-577.
Chen, L., Megow, N., Rischke, R., Stougie, L., and Verschae, J., (2015). “Optimal algorithms and a PTAS for cost-aware scheduling”. In International Symposium on Mathematical Foundations of Computer Science (pp. 211-222). Springer Berlin Heidelberg.
Ding, J. Y., Song, S., Zhang, R., Chiong, R., and Wu, C. (2016). “Parallel Machine Scheduling Under Time-of-Use Electricity Prices: New Models and Optimization Approaches. IEEE Transactions on Automation Science and Engineering, Vol. 13, No. 2, pp. 1138-1154.
Fang, K., Uhan, N. A., Zhao, F., and Sutherland, J. W., (2016). “Scheduling on a single machine under time-of-use electricity tariffs”, Annals of Operations Research, Vol. 238, pp. 199-227.
Gong, X., De Pessemier, T., Joseph, W., and Martens, L., (2015). “An energy-cost-aware scheduling methodology for sustainable manufacturing”, Procedia CIRP, 29, pp.185-190.
González, M. A., Oddi, A., and Rasconi, R., (2015). “A multi-objective memetic algorithm for solving job shops with a non-regular energy cost”, aint S ing an, Vol. 15.
Jozefowska, J., (2007). Just-in-time scheduling: models and algorithms for computer and manufacturing systems (Vol. 106). Springer Science & Business Media.
Kanet, J. J., and Sridharan, V., (2000). “Scheduling with inserted idle time: problem taxonomy and literature review”, Operations Research, Vol. 48, No. 1, pp. 99-110.
Kim, Y. D., (1993). “A new branch and bound algorithm for minimizing mean tardiness in two-machine flow shops”, Computers & Operations Research, Vol. 20, No. 4, pp. 391-401.
Liu, Y., Dong, H., Lohse, N., Petrovic, S., and Gindy, N., (2014). “An investigation into minimising total energy consumption and total weighted tardiness in job shops”, Journal of Cleaner Production, Vol. 65, pp. 87-96.
Liu, C. H., and Huang, D. H., (2014). “Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms”, International Journal of Production Research, Vol. 52, No. 2, pp. 337-352.
Luo, H., Du, B., Huang, G. Q., Chen, H., and Li, X., (2013). “Hybrid flow shop scheduling considering machine electricity consumption cost”, International Journal of Production Economics, Vol. 146, No. 2, pp. 423-439.
Manne, A. S., (1960). “On the job-shop scheduling problem”, Operations Research, Vol. 8, No. 2, pp. 219-223.
Moon, J. Y., Shin, K., and Park, J., (2013). “Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency”, The International Journal of Advanced Manufacturing Technology, Vol. 68, pp. 523-535.
Mouzon, G., and Yildirim, M.B., (2008). “A framework to minimise total energy consumption and total tardiness on a single machine”, Int. J. Sustain. Eng., Vol. 1, No. 2, pp. 105-116.
Mouzon, G., Yildirim, M.B., Twomey, J., (2007). Operational methods for minimization of energy consumption of manufacturing equipment. Int. J. Prod. Res. 45 (18-19), 4247-4271.
Schaller, J., and Valente, J. M., (2013). “A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness”, International Journal of Production Research, Vol. 51, No. 3, pp. 772-779.
Sen, T., Dileepan, P., and Gupia, J. N., (1989). “The two-machine flow shop scheduling problem with total tardiness”, Computers & operations research, Vol. 16, No. 4, pp. 333-340.
Shrouf, F., Ordieres-Meré, J., García-Sánchez, A., and Ortega-Mier, M., (2014). “Optimizing the production scheduling of a single machine to minimize total energy consumption costs”, Journal of Cleaner Production, Vol. 67, pp. 197-207.
Tan, M., Duan, B., and Su, Y., (2016). “Economic batch sizing and scheduling on parallel machines under time-of-use electricity pricing”, Operational Research, pp. 1-18.
Wan, G., and Qi, X., (2010). “Scheduling with variable time slot costs”, Naval Research Logistics (NRL), Vol. 57, No. 2, pp. 159-171.
Wang, S., Zhu, Z., Fang, K., Chu, F., and Chu, C., (2017). “Scheduling on a two-machine permutation flow shop under time-of-use electricity tariffs”, International Journal of Production Research, pp. 1-15.
Zhang, H., Zhao, F., Fang, K., and Sutherland, J. W., (2014). “Energy-conscious flow shop scheduling under time-of-use electricity tariffs”, CIRP Annals-Manufacturing Technology, Vol. 63, No. 1, pp. 37-40.
Zhang, R., and Chiong, R., (2016). “Solving the energy-efficient job shop scheduling problem: a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption”, Journal of Cleaner Production, Vol. 112, pp. 3361-3375.
Zhao, Y., Qi, X., and Li, M., (2015). “On scheduling with non-increasing time slot cost to minimize total weighted completion time”, Journal of Scheduling, pp. 1-9.
Zhong, W., and Liu, X., (2012). “A Single Machine Scheduling Problem with Time Slot Costs”, In Recent Advances in Computer Science and Information Engineering (pp. 677-681). Springer Berlin Heidelberg.
)