Uniform Parallel-Machine Scheduling with Time Dependent Processing Times
- PDF / 521,893 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 224 Views
Uniform Parallel-Machine Scheduling with Time Dependent Processing Times Juan Zou · Yuzhong Zhang · Cuixia Miao
Received: 16 January 2013 / Revised: 9 April 2013 / Accepted: 18 April 2013 / Published online: 24 May 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013
Abstract We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time. The objectives are to minimize the total completion time of all jobs and the total load on all machines. We show that the problems are polynomially solvable when the increasing rates are identical for all jobs; we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function, where the objective function is to minimize the total load on all machines. We also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time. The objective is to find a schedule which minimizes the time by which all jobs are delivered, and we propose a fully polynomial-time approximation scheme to solve this problem. Keywords Scheduling · Uniform machine · Linear deterioration · Fully polynomial time approximation scheme
1 Introduction For most scheduling problems, the processing times of jobs are considered to be constant and independent of their starting time. However, this assumption is not appropriate for the modeling of many modern industrial processes, we often encounter This work was supported by the National Natural Science Foundation of China (Nos. 11071142, 11201259), the Natural Science Foundation of Shan Dong Province (No. ZR2010AM034) and the Doctoral Fund of the Ministry of Education (No. 20123705120001). J. Zou () · Y. Zhang School of Management, Qufu Normal University, Rizhao, Shandong, China e-mail: [email protected] J. Zou · C. Miao School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong, China
240
J. Zou et al.
situations in which processing time increases over time, when the machines gradually lose efficiency. Such problems are generally known as scheduling with deterioration effects. Scheduling with linear deterioration was first considered by Browne and Yechiali [1] who assumed that the processing times of jobs are nondecreasing, start time dependent linear functions. They provided the optimal solution for the single machine when the objective is to minimize the makespan. In addition, they solved a special case when the objective function is to minimize the total weighted completion time. Mosheiov [2] considered simple linear deterioration where jobs have a fixed job-dependent growth rate but no basic processing time. He showed that most commonly applied performance criteria, such as the makespan, the total flow time, the total lateness, the sum of weighted completion time, the maximum lateness, the maximum tardiness, and the number of tardy jobs, remain polynomially
Data Loading...
