Deterministic scheduling models with machine costs and buffers

Fung, Chun Yin (Joey)

Deterministic scheduling models with machine costs and buffers

Fung, Chun Yin (Joey)

Permalink

Publication Type:: Thesis
Issue Date:: 2017

Closed Access

	Filename	Description	Size
	01front.pdf	contents and abstract	182.69 kB	Adobe PDF	View/Open
	02whole.pdf	thesis	1.07 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Fung, Chun Yin (Joey)
dc.date.accessioned	2018-03-28T04:00:47Z
dc.date.available	2020-05-25T19:26:48Z
dc.date.issued	2017
dc.identifier.uri	http://hdl.handle.net/10453/123096
dc.description	University of Technology Sydney. Faculty of Science.	en_AU
dc.description.abstract	NO FULL TEXT AVAILABLE. This thesis contains 3rd party copyright material. ----- This thesis studies a collection of optimisation problems with machine costs and/or buffers. One of the problems considered arises in capacity planning in supply chains of mineral resources. Specifically, given a particular forecasted demand, the problem requires to find a minimum cost expansion of infrastructure capacity required to satisfy this demand. This research was motivated by an existing gap in the literature on optimisation in capacity planning for supply chains of mineral resources. The developed optimisation method is designed as a matheuristic – a hybridisation of mixed integer linear programming with a metaheuristic based scheduler. Computational experiments on data, originating from a big mining company, shows the ability of the developed matheuristic to solve instances of the problem as faced in the industry, including the complexity and size of the instances. The thesis also studies a two-stage flow shop model and two two-stage flexible flow shop models for the makespan objective. Inspired by practical situations that do not fit in the traditional type of buffer, such as when a change in the mode of transportation requires storage space, or in computer systems with a shared memory, the studied models consider a type of buffer that differs from what is commonly studied in the literature. Indeed, for the type of buffer considered in this thesis, jobs occupy the buffer space from the start till the end of processing, and the amount of buffer space required differs from job to job. To the best knowledge of the author, only a few publications have studied this type of buffer and only in the two-stage flow shop setting. For the flow shop model, with the considered type of buffer, this thesis answers an open question posed by other researchers, on whether there always exists an optimal permutation schedule, i.e. an optimal schedule in which the order of job processing is identical on both machines. The thesis responds in the negative, and estimates the deviation from the optimal as a result of the restriction to the same order of processing on both machines. It is further shown that that the problem of recognising whether an instance has an optimal permutation schedule is NP-complete in the strong sense. The thesis additionally proves the complexity status of one of the special cases considered in the literature. For the two-stage flexible flow shop models, it is assumed that each stage has m identical machines. One of the models considers the situation where the buffer is shared amongst all machines, whilst the other considers the situation where first- and second-stage machines form disjoint pairs, each with a dedicated buffer. Both models assume that all operations have identical duration. For the model with shared buffer, the problem is proved to be NP-hard in the strong sense for any m ≥ 2, although it is solvable in polynomial time if m = 1. For the general case, several integer linear programming models are proposed, implementing various ideas such as symmetry breaking constraints, knapsack type cutting planes and the results of an analysis into the structure of optimal schedules. For the other model with dedicated buffers, it is proved that unless P = NP, there is no polynomial time algorithm guaranteed to give a makespan less than 4/3 of the optimal. Two integer linear programming models are presented, both of which utilise, as a sub-routine, the polynomial time algorithm for the case of equal buffers. The computational experiments indicate that the model, based on the results of graph theory, is superior overall. The research in this thesis have been presented in several refereed publications and conference presentations. On the whole, this thesis contributes a range of theoretical and computational results to the literature, spanning supply chain planning, flow shop scheduling, as well as mixed integer linear programming and optimisation procedures such as matheuristics.	en_AU
dc.format	Thesis (PhD)
dc.language.iso	en_AU	en_AU
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Deterministic scheduling models with machine costs and buffers	en_AU
dc.type	Thesis	en_AU
utslib.copyright.status	closed_access

Abstract:

NO FULL TEXT AVAILABLE. This thesis contains 3rd party copyright material. ----- This thesis studies a collection of optimisation problems with machine costs and/or buffers. One of the problems considered arises in capacity planning in supply chains of mineral resources. Specifically, given a particular forecasted demand, the problem requires to find a minimum cost expansion of infrastructure capacity required to satisfy this demand. This research was motivated by an existing gap in the literature on optimisation in capacity planning for supply chains of mineral resources. The developed optimisation method is designed as a matheuristic – a hybridisation of mixed integer linear programming with a metaheuristic based scheduler. Computational experiments on data, originating from a big mining company, shows the ability of the developed matheuristic to solve instances of the problem as faced in the industry, including the complexity and size of the instances. The thesis also studies a two-stage flow shop model and two two-stage flexible flow shop models for the makespan objective. Inspired by practical situations that do not fit in the traditional type of buffer, such as when a change in the mode of transportation requires storage space, or in computer systems with a shared memory, the studied models consider a type of buffer that differs from what is commonly studied in the literature. Indeed, for the type of buffer considered in this thesis, jobs occupy the buffer space from the start till the end of processing, and the amount of buffer space required differs from job to job. To the best knowledge of the author, only a few publications have studied this type of buffer and only in the two-stage flow shop setting. For the flow shop model, with the considered type of buffer, this thesis answers an open question posed by other researchers, on whether there always exists an optimal permutation schedule, i.e. an optimal schedule in which the order of job processing is identical on both machines. The thesis responds in the negative, and estimates the deviation from the optimal as a result of the restriction to the same order of processing on both machines. It is further shown that that the problem of recognising whether an instance has an optimal permutation schedule is NP-complete in the strong sense. The thesis additionally proves the complexity status of one of the special cases considered in the literature. For the two-stage flexible flow shop models, it is assumed that each stage has m identical machines. One of the models considers the situation where the buffer is shared amongst all machines, whilst the other considers the situation where first- and second-stage machines form disjoint pairs, each with a dedicated buffer. Both models assume that all operations have identical duration. For the model with shared buffer, the problem is proved to be NP-hard in the strong sense for any m ≥ 2, although it is solvable in polynomial time if m = 1. For the general case, several integer linear programming models are proposed, implementing various ideas such as symmetry breaking constraints, knapsack type cutting planes and the results of an analysis into the structure of optimal schedules. For the other model with dedicated buffers, it is proved that unless P = NP, there is no polynomial time algorithm guaranteed to give a makespan less than 4/3 of the optimal. Two integer linear programming models are presented, both of which utilise, as a sub-routine, the polynomial time algorithm for the case of equal buffers. The computational experiments indicate that the model, based on the results of graph theory, is superior overall. The research in this thesis have been presented in several refereed publications and conference presentations. On the whole, this thesis contributes a range of theoretical and computational results to the literature, spanning supply chain planning, flow shop scheduling, as well as mixed integer linear programming and optimisation procedures such as matheuristics.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/123096