Kontrol edilebilir işlem süreleriyle makine çizelgelemede maliyet/zaman ilişkileri

Processing time controllability is a critical aspect in scheduling decisionssince most of the scheduling practice in industry allows controlling processingtimes. A very well known example is the computer numerically controlled (CNC)machines in flexible manufacturing systems. Selected processing times for agiven set of jobs determine the manufacturing cost of the jobs and stronglyaffect their scheduling performance. Hence, when making processing time andscheduling decisions at the same time, one must consider both the manufacturingcost and the scheduling performance objectives.In this thesis, we have studiedsuch bicriteria scheduling problems in various scheduling environmentsincludingsingle, parallel and non-identical parallel machine environments. We haveincluded some regular scheduling performance measures such as total weightedcompletion time and makespan. We have considered the convexmanufacturing cost function of CNC turning operation.We have provided alternative methods to find efficient solutions in eachproblem. We have particularly focused on the single objective problems to getefficient solutions, called the $\epsilon$-constraintapproach. We have provided efficientformulations for the problems and shown useful properties which led us todevelop fast heuristics to generate set of efficient solutions.In this thesis, taking another point of view, we have also studied a conicquadratic reformulation of a machine-job assignment problem with controllableprocessing times. We have considered a convex compression cost function foreach job and solved a profit maximization problem. The convexity of costfunctions is a major source of difficulty in finding optimal integer solutionsin this problem, but our strengthened conic reformulation has eliminated thisdifficulty. Our reformulation approach is sufficiently general so that it canalso be applied to other mixed 0-1 optimization problems with separable convexcost functions. Our computational results demonstrate that the proposed conicreformulation is very effective for solving the machine-job assignment problemwith controllable processing times to optimality.Finally, in this thesis, we have considered rescheduling with controllableprocessing times. In particular, we show that in contrast to fixed processingtimes, if we have the flexibility to control the processing times of the jobs,we can generate alternative reactive schedules in response to a disruptionsuch as machine breakdown. We consider a non-identical parallel machiningenvironment where processing times of the jobs are compressible at a certaincost which is a convex function of the compression on the processing time.When rescheduling, it is critical to catch up the initial schedule as soon aspossible by reassigning the jobs to the machines and changing their processingtimes. On the other hand, one must keep the total cost of the jobs at minimum.We present alternative match-up scheduling problems dealing with thistrade-off. We use the strong conic reformulation approach insolving these problems. We further provide fast heuristic algorithms.