Research On Some New Scheduling Problems With Due Date Assignment

Scheduling is one of the most active branches in combinatorial optimization. Its background is mainly machine manufacture, subsequenely variants of the scheduling problems have found many applications in areas such as transportation dispatch,production management and computer systems. Scheduling problems with due date assignment or due-window assignment has received considerable attention in recent years,which have made a lot of results. The aim of this paper is to investigate two kinds of scheduing problems: scheduing with learning effects, due date assignment and past-sequence-dependent set up times, and scheduing with deteriorating maintenance activity, due-window assignment and past-sequence-dependent set up times. The structure of the paper is organized as follows.In Chapter 1, some notations, definitions and basic background information about the subject are introduced, and then the main research results and innovation in this dissertation have been summarized.In Chapter 2, we addresses the single-machine scheduling problem with simultaneous consideration of due date assignment, past-sequence-dependent(p-s-d) set up times, and position-dependent learning effects. By past-sequence-dependent set up times, we mean that the setup time of a job is proportional to the sum of the processing time. Specifically,we study five versions of problem that differ in terms of the objective function and due date assignment method being used. We derive the structural properties of the optimal schedules of the considered problems and provide polynomial-time solution algorithms.In Chapter 3, in order to more realistically model a production system, we investigate the problem of common due-window assignment and past-sequence-dependent(p-s-d)setup times and a deteriorating maintenance activity simultaneously. The objective is to find jointly the optimal maintenance location, the optimal location and size of the due-window, and the optimal job sequence to minimize the total earliness, tardiness, and due-window starting time and size costs.In Chapter 4, the main work of this paper is summarized, and the future work is given.