Machine Scheduling With An Availability Constraint In Supply Chain Management

Machine scheduling is an important topic in supply chain management and gainsmuch attention. The machine scheduling with an availability constraint is one of thenew models which important and difficulty. This thesis concerns the design ofapproximation algorithm and heuristic algorithm in machine scheduling with anavailability constraint and delivery coordination in two-stage supply chain. And testthe performance of the algorism according to the proof and numerical computation.The thesis is split up into four chapters. We first introduce some preliminaryconcepts related to the scheduling problem and supply chain management andsummarize recent results of supply chain scheduling problem with the size of jobcoordination in chapter1.In chapter2, we consider single machine scheduling problem with oneavailability constraint of the size of job coordination, in which the size of jobs isdifferent and delivered by a capacitated vehicle to a single customer. In this model theprocessing time are un-proportion with the job size, it denotedby1â†'D, k=1|v=1, c=z, nr=a|C_max, this problem is NP-hard. We give a heuristicalgorithm and analysis its performance by using numerical method.In chapter3, we consider a single-machine scheduling problem with periodicmaintenance activities of the size of job coordination, in which jobs are first processedon a single machine and the processing time are proportional. It denoted by1â†'D, k=1|v=1, c=z=π∕u, nr=pm, p_j=us_j|C_max. We design LPT algorithm forthis model and get the worst-case ratio is2.In chapter4, we summarize this thesis and give the future study and research.