Study On Scheduling Problems With Controllable Job-processing Times

In most traditional deterministic scheduling problems, job-processing times are re-garded as discrete constant known in advance, and the scheduling algorithm only needs to assign jobs to machines and to determine the job-processing permutation on each machine. However, in many realistic manufacturing environments, job-processing times can be con-trolled by allocating extra resource to jobs. Examples of such resource includes human resource, electricity power, gas and cash. The introduction of controllable job-processing times shortens the gap between theoretical research and realistic application, and enhances the flexibility of the scheduling algorithm. However, as more decision variables are added, the computational complexity of the scheduling problems also increases greatly. In fact, as the generalization of the traditional scheduling problems that have constant job-processing times, most of the scheduling problems with controllable job-processing times are NP-hard. For this reason, although the first research report of this field can be traced back to 1980, so far most research work still concerns on relatively simple scheduling problems, most of them focus on single machine environments.The great gap between realistic requirement and theoretical research inspired our work. In this paper, we concern on several single machine and multi-machine deterministic scheduling problems with controllable job-processing times, and provide optimal or near optimal solution for problems of the real-world size. The accomplished work is only the start of a long-term research on this interesting and valuable field, further research work will be continued. Following research result will be introduced in this paper:1. Single machine scheduling with independent job release dates and due dates. The scheduling algorithm is intended to avoid delay of shipment and to minimize total resource consumption.(a) We introduced polynomial time optimal resource allocation algorithms for schedul-ing problems in discrete time environment, and problems in continuous time envi- ronment with linear resource consumption function and non-linear convex resource consumption function;(b) We introduced a branch and bound algorithm for searching for the optimal job-processing permutation for small-and media-sized problems;(c) We introduced a tabu-search algorithm for searching for the optimal or near op-timal job-processing permutation for the real-world-sized problems.2. Single machine scheduling with total tardiness criteria. The scheduling algorithm is intended to make sure that total tardiness will not exceed a given requirement while the total resource consumption is minimized. We introduced a polynomial time optimal algorithm for the special case where jobs have a common due date.3. Parallel machine scheduling with independent job release dates and due dates. The algorithm is intended to avoid delay of shipment and to minimize total resource con-sumption. We extended the researching result on single machine scheduling problem to parallel machines, and introduced a tabu-search algorithm to provide optimal or near optimal solution for the real-world-sized problems.4. Parallel machine scheduling with job-processing precedence constraints. The algo-rithm is intended to provide a solution with makespan no larger than the requirement and minimum total resource consumption.(a) We introduced a greedy algorithm for the resource allocation problem in discrete time environment;(b) We introduced a tabu-search algorithm to provide solution for real-world-sized problems.The research work of this paper is just the beginning of our work in the field of scheduling jobs with controllable job-processing times. In this field, there exist still a great number of research work that is waiting for exploration, which is the main reason that the field is full of attraction. Thus, in the following work we will devote ourselves deeper into this field, and work for further achievement both in theory and in application.