Algorithms For Some Scheduling Problems With Machine Availability Constraints

The design and analysis of algorithms for the scheduling problems with machine availability constraints are studied in this paper. We first research the scheduling prob-lems with machine availability constraints, and then consider the supply-chain scheduling problems. We mainly focus on the scheduling problems in offline and online cases. The objective functions referred in this paper are to minimize makespan, total completion time, maximum delivery time and total delivery time.This paper consists of six chapters. The first chapter gives the basic definitions of combinational optimization and scheduling problems. Then, some classic scheduling problems and the development of the scheduling problems with machine availability con-straints and the supply-chain scheduling problems are introduced.In the second chapter, we first consider a single-machine scheduling with an availabil-ity constraint to minimize makespan. We design an algorithm with a worst-case ratio of 4/3 and a dynamic programming for the offline version and an optimal online algorithm for the online version. Then, we study a single-machine scheduling with an availabil-ity constraint to minimize total completion time and design an algorithm with a tight worst-case ratio of 17/15 and runtime of O(n log n).We study a two-machine scheduling problem in the third chapter. One machine has an availability constraint and the other is always available. Jobs are not allowed to resume. The objective is to minimize makespan. An FPTAS (Fully Polynomial Time Approximation Scheme) is provided.The fourth chapter deals with a two-machine scheduling problem. One machine has periodic availability constraints and the other is always available. The objective is to minimize makespan. We provide two 4/3-approximation algorithms for the non-resumable and resumable cases, respectively. Then, we propose an online optimal algorithm for the online resumable problem.Chapter 5 considers the supply-chain scheduling problems where the processing ma-chine has an availability constraint. There is one vehicle with capacity to deliver jobs. Jobs are not allowed to resume. In the first production then delivery system, we propose an algorithm with a worst-case ratio of 4/3 when the objective is to minimize the time by which the vehicle delivers all jobs to the customer and returns to the manufacturing cen-ter. We also provide an algorithm with a worst-case ratio of 3/2 when the objective is to minimize total delivery time. In the first delivery then production system, an algorithm with a worst-case ratio of 4/3 is provided when the objective is to minimize makespan.The sixth chapter studies the supply-chain scheduling problems with machine avail-ability constraints. The machine has periodic availability constraints. There is a vehicle with capacity. Jobs are not allowed to resume. For the first production then delivery system, the objective is to minimize the time by which the vehicle takes all jobs to the cus-tomer and returns to the manufacturing center. We give a best possible polynomial-time approximation algorithm. For the first delivery then production system, the objective is to minimize makespan. We also propose a best possible polynomial-time approximation algorithm.