Search

We consider single-machine scheduling problems with time and position dependent job processing times. In many industrial settings, the processing time of a job changes due to either job deterioration over time or machine/worker's learning through experiences. In the models we study, each job has its normal processing time. However, a job's actual processing time depends on when its processing starts and how many jobs have completed before its start. We prove that the classical SPT (Shortest Processing Time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time, the maximum lateness, and the discounted total weighted completion time, we present heuristic sequencing rules and analyze the worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights. [ABSTRACT FROM AUTHOR]

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost of completion times and the cost of compression. The complexity of this problem is still unknown. In Part I of this paper, the authors have considered a special case where the compression times and the compression costs are equal among all jobs. Such a problem appears polynomially solvable by developing an O( n 2 ) algorithm. In this part(Part II), a general case where the controllable processing times and the compression costs are not equal is discussed. Authors propose here two heuristics with the first based on some previous work and the second based on the algorithm developed in Part I. Computational results are presented to show the efficiency and the robustness of these heuristics. [ABSTRACT FROM AUTHOR]

This report is virtually the appendix part of the author’s previous paper which includes the proofs for the theorems and lemmas. [ABSTRACT FROM AUTHOR]

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented. [ABSTRACT FROM AUTHOR]

In this paper, the problem of sequencing jobs on a single machine to minimize the weighted number of tardy jobs is considered. Some new dominances between jobs are proposed and studied. A new branch and bound algorithm that can solve large problems, e.g. 85 jobs, is presented. [ABSTRACT FROM AUTHOR]