We consider a single machine scheduling problem to minimize the completion time variance. This roblem is known to be NP-hard. We prove that if $p_{n-1} = p_{n-2$, then there is an optimal solution of the form $(n,n-2,n-3,…,n-4,n-1)$. A new lower bound are proposed for solving the problem. The test on more than 4000 instances shows … Read more
Services must be delivered with high punctuality to be competitive. The classical scheduling theory offers to minimize the total earliness and tardiness of jobs to deliver punctual services. In this study, we developed a fully polynomial-time optimal algorithm to transform a given sequence, the permutation of jobs, into its corresponding minimum cost schedule, the timing … Read more
We consider a special class of resource-constrained single machine scheduling problems. In the classical scheduling context, resource types are classi ed into renewable and non-renewable; however, a large variety of real-world problems may not fit into one of these classes, e.g., labor regulations in project scheduling, budget allocation to different phases of a construction project, and … Read more
This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP) while incorporating techniques from … Read more